二叉搜索树

二叉搜索树的简介：

• 二叉搜索树它是二叉树的一种类别，其节点按特定顺序排列。这也称为有序二叉树。
• 在二叉搜索树中，左子树中所有节点的值小于根的值。
• 类似地，右子树中所有节点的值大于或等于根的值。
• 此规则将递归地应用于根的所有左子树和右子树。

二叉搜索树如上图所示。在二叉搜索树上应用的约束，可以看到根节点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