二叉搜索樹

二叉搜索樹的簡介：

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

二叉搜索樹如上圖所示。在二叉搜索樹上應用的約束，可以看到根節點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