二叉查找树（binary search tree）实现详解二叉查找树|数据结构

本文概述

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

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

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

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

问：使用以下数据元素创建二进制搜索树。
43, 10, 79, 90, 12, 54, 11, 9, 50

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

下图显示了使用给定元素创建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 = http://www.srcmini.com/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); elseroot-> 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; elsecur = 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; elseparent-> right = NULL; }elseroot = NULL; free(cur); }else if (cur-> left & & cur-> right){Node* succ= findMinimum(cur- > right); int val = succ-> data; deletion(root, succ-> data); cur-> data = http://www.srcmini.com/val; }else{Node* child = (cur-> left)? Cur- > left: cur-> right; if (cur != root){if (cur == parent-> left)parent-> left = child; elseparent-> right = child; }elseroot = 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; }

【二叉查找树（binary search tree）实现详解】输出：

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