个性化阅读
专注于IT技术分析

二叉查找树(binary search tree)实现详解

点击下载

本文概述

  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的过程。

二叉查找树

二进制搜索树上的操作

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

序号 运作方式 描述
1 在BST中搜索 在二进制搜索树中查找某些特定元素的位置。
2 插入BST 在适当的位置向二进制搜索树添加一个新元素, 以免破坏BST的属性。
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
赞(0)
未经允许不得转载:srcmini » 二叉查找树(binary search tree)实现详解

评论 抢沙发

评论前必须登录!