將二叉樹轉換為二叉搜尋樹
二叉樹是一種非線性資料結構。它被稱為二叉樹，因為每個節點最多有兩個子節點。這些子節點被稱為左子和右子。它也可以解釋為一個不定向圖，其中最上面的節點稱為根。二叉搜尋樹(BST)是一種具有特殊屬性的二叉樹，它有助於以排序的方式保持資料的組織。
在本教程中，我們將討論如何將二叉樹轉換為二叉搜尋樹，同時保持二叉樹的原始結構。
將二叉樹轉換為二叉搜尋樹的演算法
-
建立一個名為
arr的陣列來儲存二叉樹節點的順序遍歷。 -
使用任何排序演算法（合併排序 O(nlogn)、快速排序 O(n^2)、插入排序 O(n^2)等）對
arr進行排序。 -
再次對樹進行順序遍歷，並將排序陣列
arr中的元素儲存在二叉樹中，得出 BST。
二叉樹轉換為 BST 圖解
-
我們在根節點
4上呼叫順序遍歷。遞迴向左遍歷到達節點1，它是最左的節點，並將其包含在我們的輸出中；由於它是根節點，沒有左節點，我們回溯到節點2，並將其包含在我們的遍歷中。這樣，我們遍歷整棵樹，並將按順序遍歷的結果以[1，2，3，5，4，6]的形式儲存在陣列arr中。 -
使用任意排序演算法對陣列
arr進行排序，得到[1，2，3，4，5，6]。 -
我們再次呼叫順序遍歷，將排序後的陣列
arr儲存回二叉樹中，得到我們的 BST。
二叉樹轉換為二叉搜尋樹的實現
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *left, *right; Node(int x) { this->data = x; this->left = this->right = NULL; } }; vector<int> v; void inorder(Node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); } } void storetree(Node* root, int i = 0) { if (!root) { return; } storetree(root->left); v.push_back(root->data); storetree(root->right); } void restoretree(Node* root, int& i) { if (!root) { return; } restoretree(root->left, i); root->data = v[i]; i++; restoretree(root->right, i); } void converttoBST(Node* root) { if (!root) { return; } storetree(root); sort(v.begin(), v.end()); int i = 0; restoretree(root, i); } int main() { Node* root = new Node(3); root->left = new Node(1); root->right = new Node(7); root->left->left = new Node(4); root->left->right = new Node(5); root->left->left->right = new Node(2); root->right->left = new Node(6); root->right->right = new Node(9); root->right->right->left = new Node(8); cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl; converttoBST(root); cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl; } 將二叉樹轉換為 BST 演算法的複雜度
時間複雜度
- 平均情況
我們將陣列儲存在 sorted 中，並將 sorted 陣列儲存回二叉樹，進行無序遍歷的時間複雜度為 O(n)。但是，對陣列進行排序的複雜度是 O(nlogn)，因此總複雜度給定為 O(nlogn)+2*O(n)。時間複雜度為 O(nlogn)。
- 最佳情況
最佳情況下的時間複雜度為 O(n)。當給定的二叉樹已經是一個 BST 時，我們做無序遍歷來實現它，而且不需要排序操作。
- 最壞情況
最壞情況下的時間複雜度為 O(nlogn)。
空間複雜度
由於遞迴呼叫所需的額外空間，該演算法的空間複雜度為 O(n)。
Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe
作者： Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn