二元搜尋樹

二元搜尋樹的簡介：

• 二元搜尋樹它是二元樹的一種類別，其節點按特定順序排列。這也稱為有序二元樹。
• 在二元搜尋樹中，左子樹中所有節點的值小於根的值。
• 類似地，右子樹中所有節點的值大於或等於根的值。
• 此規則將遞回地應用於根的所有左子樹和右子樹。

二元搜尋樹如上圖所示。在二元搜尋樹上應用的約束，可以看到根節點30在其左子樹中不包含任何大於或等於30的值，並且在其右子樹中也不包含任何小於30的值的子樹節點值。

使用二元搜尋樹的優點

搜尋在二元搜尋樹中變得非常有效，因為得到每個步驟的提示，哪個子樹包含所需元素。
與陣列和連結串列相比，二元搜尋樹被認為是有效的資料結構。 在搜尋過程中，它會在每一步刪除半個子樹。 在二元搜尋樹中搜尋元素需要o(log2n)時間。 在最壞的情況下，搜尋元素所花費的時間是0(n)。
與陣列和連結串列中的操作相比，它還加快了插入和刪除操作。

問題： 如何使用以下資料元素建立二元搜尋樹。

43, 10, 79, 90, 12, 54, 11, 9, 50

• 首先，將43插入樹中並作為樹的根。
• 讀取下一個元素，如果它小於根節點元素，則將其作為左子樹的根插入。
• 否則，將其作為右子樹的根插入。

使用給定元素建立二元搜尋樹的過程如下圖所示。

二元搜尋樹的操作

在二元搜尋樹上可以執行許多操作。如下表所示 -

二元搜尋樹的C語言實現程式碼

#include <iostream>  
#include <stdlib.h>  
using namespace std;  
struct Node {  
    int data;  
    Node *left;  
    Node *right;  
};  
Node* create(int item)  
{  
    Node* node = new Node;  
    node->data = item;  
    node->left = node->right = NULL;  
    return node;  
}  

void inorder(Node *root)  
{  
    if (root == NULL)  
        return;  

    inorder(root->left);  
    cout<< root->data << "   ";  
    inorder(root->right);  
}  
Node* findMinimum(Node* cur)  
{  
    while(cur->left != NULL) {  
        cur = cur->left;  
    }  
    return cur;  
}  
Node* insertion(Node* root, int item)  
{  
    if (root == NULL)  
        return create(item);  
    if (item < root->data)  
        root->left = insertion(root->left, item);  
    else  
        root->right = insertion(root->right, item);  

    return root;  
}  

void search(Node* &cur, int item, Node* &parent)  
{  
    while (cur != NULL && cur->data != item)  
    {  
        parent = cur;  

        if (item < cur->data)  
            cur = cur->left;  
        else  
            cur = cur->right;  
    }  
}  

void deletion(Node*& root, int item)  
{  
    Node* parent = NULL;  
    Node* cur = root;  

    search(cur, item, parent);  
    if (cur == NULL)  
        return;  

    if (cur->left == NULL && cur->right == NULL)  
    {  
        if (cur != root)  
        {  
            if (parent->left == cur)  
                parent->left = NULL;  
            else  
                parent->right = NULL;  
        }  
        else  
            root = NULL;  

        free(cur);       
    }  
    else if (cur->left && cur->right)  
    {  
        Node* succ  = findMinimum(cur- >right);  

        int val = succ->data;  

        deletion(root, succ->data);  

        cur->data = val;  
    }  

    else  
    {  
        Node* child = (cur->left)? Cur- >left: cur->right;  

        if (cur != root)  
        {  
            if (cur == parent->left)  
                parent->left = child;  
            else  
                parent->right = child;  
        }  

        else  
            root = child;  
        free(cur);  
    }  
}  

int main()  
{  
   Node* root = NULL;  
   int keys[8];  
   for(int i=0;i<8;i++)  
    {  
    cout << "Enter value to be inserted";  
    cin>>keys[i];  
        root = insertion(root, keys[i]);  
    }  

    inorder(root);  
    cout<<"\n";  
    deletion(root, 10);  
    inorder(root);  
    return 0;  
}

執行上面範例程式碼，得到以下結果：

Enter value to be inserted? 10
Enter value to be inserted? 20
Enter value to be inserted? 30
Enter value to be inserted? 40
Enter value to be inserted?  5 
Enter value to be inserted? 25
Enter value to be inserted? 15
Enter value to be inserted?  5

5    5    10    15    20    25    30    40    
5    5    15    20    25    30    40