將二叉樹轉換為二叉搜尋樹
Harshit Jindal
2023年1月30日
2021年2月28日
二叉樹是一種非線性資料結構。它被稱為二叉樹,因為每個節點最多有兩個子節點。這些子節點被稱為左子和右子。它也可以解釋為一個不定向圖,其中最上面的節點稱為根。二叉搜尋樹(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)
。
Author: 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