將二叉樹轉換為二叉搜尋樹

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 將二叉樹轉換為二叉搜尋樹的演算法
  2. 二叉樹轉換為 BST 圖解
  3. 二叉樹轉換為二叉搜尋樹的實現
  4. 將二叉樹轉換為 BST 演算法的複雜度
將二叉樹轉換為二叉搜尋樹

二叉樹是一種非線性資料結構。它被稱為二叉樹,因為每個節點最多有兩個子節點。這些子節點被稱為左子和右子。它也可以解釋為一個不定向圖,其中最上面的節點稱為根。二叉搜尋樹(BST)是一種具有特殊屬性的二叉樹,它有助於以排序的方式保持資料的組織。

在本教程中,我們將討論如何將二叉樹轉換為二叉搜尋樹,同時保持二叉樹的原始結構。

將二叉樹轉換為二叉搜尋樹的演算法

  • 建立一個名為 arr 的陣列來儲存二叉樹節點的順序遍歷。
  • 使用任何排序演算法(合併排序 O(nlogn)、快速排序 O(n^2)、插入排序 O(n^2)等)對 arr 進行排序。
  • 再次對樹進行順序遍歷,並將排序陣列 arr 中的元素儲存在二叉樹中,得出 BST。

二叉樹轉換為 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)

Harshit Jindal avatar Harshit Jindal avatar

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

相關文章 - Data Structure

相關文章 - Binary Tree

相關文章 - Binary Search Tree