二叉查找树（binary search tree）实现详解

本文概述

• 使用二叉搜索树的优点
• 二进制搜索树上的操作
• 实施BST操作的程序

1. 二进制搜索树可以定义为一类二进制树, 其中节点以特定顺序排列。这也称为有序二叉树。
2. 在二叉搜索树中, 左子树中所有节点的值小于根的值。
3. 同样, 右侧子树中所有节点的值都大于或等于根的值。
4. 此规则将递归应用于根的所有左子树和右子树。

上图中显示了二进制搜索树。作为对BST施加的约束, 我们可以看到根节点30在其左子树中不包含任何大于或等于30的值, 并且在其右子树中也不包含任何小于30的值。 -树。

使用二叉搜索树的优点

1. 在二叉搜索树中搜索变得非常高效, 因为我们在每一步都会得到一个提示, 即哪个子树包含所需的元素。
2. 与数组和链表相比, 二进制搜索树被认为是有效的数据结构。在搜索过程中, 它会在每个步骤中删除一半的子树。在二叉搜索树中搜索元素需要o（log2n）时间。在最坏的情况下, 搜索元素所需的时间为0（n）。
3. 与数组和链表中的插入和删除操作相比, 它还加快了插入和删除操作的速度。

问：使用以下数据元素创建二进制搜索树。

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

1. 将43插入到树中作为树的根。
2. 读取下一个元素（如果小于根节点元素）, 则将其插入到左子树的根。
3. 否则, 将其插入为右侧子树右侧的根。

下图显示了使用给定元素创建BST的过程。

二进制搜索树上的操作

在二进制搜索树上可以执行许多操作。

实施BST操作的程序

#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