二叉搜索树 Myth丶恋晨 2022-09-30 06:45 157阅读 0赞 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: **它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。** 这个是百度百科上的一个定义,个人认为还是比较易懂的,简单点来说二叉搜索树就是要么是一个空空树,要么是一棵二叉树,如果存在左子树,那么左子树上的所有节点的值都小于根节点的值,如果存在右子树,那么右子树的所有节点的值都大于根节点的值,并且左右子树都是二叉搜索树。 好吧,不管我解释的清不清楚,下面来看一张图就知道了: ![这里写图片描述][SouthEast] 一个典型的二叉搜索树。对照定义看看就很清楚了,那么,问题来了,怎么构造二叉搜索树呢?根据定义,我们应该能猜出个大概:比较当前节点,如果小于当前节点的值,那么对左子树进行比较,如果大于,那么对右子树进行比较。 下面给出代码: void insert(int n) { // 插入一个节点值为 n 的新节点 if(!root) { // 如果根节点为空,那么新建一个节点作为根节点 root = new Node; root->parent = root->left = root->right = NULL; root->key = n; return ; } Node *now = root; Node *parent = NULL; while(now) { parent = now; if(n < now->key) { // 如果要寻找的值小于当前节点的值,那么插入到左节点 now = now->left; } else if(n > now->key) { // 如果要寻找的值大于当前节点的值,那么插入到右节点 now = now->right; } else { // 如果等于那么证明二叉搜索树中存在这个值的节点 return ; } } now = new Node; now->parent = parent; now->left = NULL; now->right = NULL; now->key = n; // 新建一个节点并且对其赋值 if(n < parent->key) { // 新建的节点作为左子节点或者右子节点 parent->left = now; } else { parent->right = now; } } 那么对二叉搜索树中的节点值进行搜索呢?这个跟插入是差不多的,分别搜索当前节点、左右子树、直到找到或者没找到,返回对应的值: // 查找节点值为 n 的节点并且返回(没找到返回NULL) Node *find(int n) { Node *now = root; while(now) { if(now->key == n) { // 等于则直接返回这个节点 return now; } else if(now->key > n) { // 小于则找左节点 now = now->left; } else { // 大于则找右节点 now = now->right; } } return NULL; // 如果没找到返回 NULL } 如果要对二叉搜索树中的节点节点值进行删除呢?其实核心思想也是对节点的值进行寻找,如果找到了就删除这个节点并且连接对应节点,那么怎么确定这个“对应节点”呢?我们要注意定义中说明的:一个二叉搜索树的左右子树也是二叉搜索树(如果存在)。**这里我们可以使用这个节点的左子树中的“最大值”所在的节点或者这个节点的右子树中的“最小值”所在的节点来代替这个要删除的节点的位置。**但是这里要注意的是要删除的节点的情况:没有子节点、只有一个节点、有两个节点,我们要对这三种情况都要考虑到并进行对应的处理,下面在代码中说明: // 删除节点值为 n 的节点,成功就返回 true,否则返回 false bool erase(int n) { Node *now = root; Node *find = NULL; // 代替要删除的节点的位置的节点 while(now) { if(now->key == n) { // 如果找到这个值所在节点 if(now->left) { // 如果左子树不为空 find = now->left; // 找到左子树 // 寻找左子树中值最大的节点(最右边的) while(find->right) { find = find->right; } } else if(now->right) { // 如果右子树不为空 find = now->right; // 找到右子树 // 寻找右子树中值最小的节点(最左边的) while(find->left) { find = find->left; } } if(now->parent) { // 如果这个节点有父节点 if(now->parent->left == now) { now->parent->left = find; } else { now->parent->right = find; } } if(find) { // 如果删除的节点是叶子节点(无左右子树),那么要考虑 find 是否为空 find->parent = now->parent; // 替换节点内容 } if(root == now) { // 如果删除的是根结点 root = find; } if(now->left == find) { // 连接 find 节点和 now 的另外一个子节点 find->right = now->right; find->right->parent = find; } else { find->left = now->left; find->left->parent = find; } delete now; now = NULL; return true; // 找到值并且删除成功返回 true } else if(now->key > n) { now = now->left; } else { now = now->right; } } return false; // 没删除成功返回 false } Ok,基本原理和操作都讲完了,下面上完整代码: #include <iostream> using namespace std; struct Node { // 储存二叉树节点信息的结构体 struct Node *parent; struct Node *left; struct Node *right; int key; }; Node *root = NULL; void insert(int n) { // 插入一个节点值为 n 的新节点 if(!root) { // 如果根节点为空,那么新建一个节点作为根节点 root = new Node; root->parent = root->left = root->right = NULL; root->key = n; return ; } Node *now = root; Node *parent = NULL; while(now) { parent = now; if(n < now->key) { // 如果要寻找的值小于当前节点的值,那么插入到左节点 now = now->left; } else if(n > now->key) { // 如果要寻找的值大于当前节点的值,那么插入到右节点 now = now->right; } else { // 如果等于那么证明二叉搜索树中存在这个值的节点 return ; } } now = new Node; now->parent = parent; now->left = NULL; now->right = NULL; now->key = n; // 新建一个节点并且对其赋值 if(n < parent->key) { // 新建的节点作为左子节点或者右子节点 parent->left = now; } else { parent->right = now; } } // 删除节点值为 n 的节点,成功就返回 true,否则返回 false bool erase(int n) { Node *now = root; Node *find = NULL; // 代替要删除的节点的位置的节点 while(now) { if(now->key == n) { // 如果找到这个值所在节点 if(now->left) { // 如果左子树不为空 find = now->left; // 找到左子树 // 寻找左子树中值最大的节点(最右边的) while(find->right) { find = find->right; } } else if(now->right) { // 如果右子树不为空 find = now->right; // 找到右子树 // 寻找右子树中值最小的节点(最左边的) while(find->left) { find = find->left; } } if(now->parent) { // 如果这个节点有父节点 if(now->parent->left == now) { now->parent->left = find; } else { now->parent->right = find; } } if(find) { // 如果删除的节点是叶子节点(无左右子树),那么要考虑 find 是否为空 find->parent = now->parent; // 替换节点内容 } if(root == now) { // 如果删除的是根结点 root = find; } if(now->left == find) { // 连接 find 节点和 now 的另外一个子节点 find->right = now->right; find->right->parent = find; } else { find->left = now->left; find->left->parent = find; } delete now; now = NULL; return true; // 找到值并且删除成功返回 true } else if(now->key > n) { now = now->left; } else { now = now->right; } } return false; // 没删除成功返回 false } // 查找节点值为 n 的节点并且返回(没找到返回NULL) Node *find(int n) { Node *now = root; while(now) { if(now->key == n) { // 等于则直接返回这个节点 return now; } else if(now->key > n) { // 小于则找左节点 now = now->left; } else { // 大于则找右节点 now = now->right; } } return NULL; // 如果没找到返回 NULL } void inOrder(Node *now) { // 中序遍历,即为从小到大输出节点值 if(now) { inOrder(now->left); cout << now->key << " "; inOrder(now->right); } } int main() { int n, key; cin >> n; for(int i = 0; i < n; i++) { cin >> key; insert(key); } cout << "当前二叉搜索树:" << endl; inOrder(root); cout << endl << "输入要删除的值:" << endl; cin >> key; if(erase(key)) { cout << "删除成功" << endl; } else { cout << "删除失败" << endl; } cout << "当前二叉搜索树:" << endl; inOrder(root); cout << endl << "输入要查找的值:"; cin >> key; Node *f = find(key); if(f) { cout << "找到节点的值:"; cout << f->key << endl; } else { cout << "没找到该节点!" << endl; } return 0; } 运行结果: ![这里写图片描述][SouthEast 1] 对于测试数据,和我们的预期结果还是一样的。小伙伴们有兴趣可以试试别的数据检测一下。这里提一下,二叉搜索树这种数据结构被广泛应用于 C++ STL 中的一些容器中(set、map),当然,它们的内部实现肯定不止这一种数据结构,有兴趣的小伙伴可以看一下这些容器的源码。 如果博客中有什么不正确的地方,还请多多指点。如果觉得我写的不错,那么请点个赞支持我吧。 谢谢观看。。。 [SouthEast]: /images/20220708/256d9f332734427bb54795ef3f1b5e90.png [SouthEast 1]: /images/20220708/657e08a316194c90829fb66037ed0f7d.png
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 73 阅读
相关 二叉搜索树 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 158 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 156 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 244 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 202 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 241 阅读
相关 二叉搜索树 思路 二叉排序树,二叉搜索树好像都行,原理应该都懂,比较基础,但要写出来还是有相当大的难度的。 查找 查找比较简单,基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 230 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 254 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 233 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 300 阅读
还没有评论,来说两句吧...