【筆記】二分搜尋樹（Binary Search Tree）

基本介紹

定義

• 父節點的左子節點（left node）皆小於父節點。
• 父節點的右子節點（right node）皆大於父節點。
• 任意節點的左右子樹都符合 BST 的定義。
• 不存在等值的資料。

圖例：

時間複雜度

演算法	平均	最差
空間	O(n)	O(n)
搜尋	O(log n)	O(n)
插入	O(log n)	O(n)
刪除	O(log n)	O(n)

了解更多點我

實作

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 中序
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

Node* add_node(Node* new_node, int n) {
    if (new_node == NULL) {
        new_node = new Node;
        new_node->data = n;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    }
    return new_node;
}

// BST 的遞迴
Node* input_data(Node* btree, int n) {
    if (btree == NULL) {
        btree = add_node(btree, n);
    }

    if (n < btree->data) {
        btree->left = input_data(btree->left, n);
    } else if (n > btree->data) {
        btree->right = input_data(btree->right, n);
    }

    return btree;
}

int main() {
    Node* binary_tree = NULL;
    int n;
    while (cin >> n) {
        if (n == -1) break;
        binary_tree = input_data(binary_tree, n);
    }
    inorder(binary_tree);
    return 0;
}