二叉排序树的定义及基本操作（构造、查找、插入、删除）递归及非递归算法 文章目录 二叉排序树的定义二叉排序树的查找二叉排序树的插入二叉排序树的构造二叉排序树的删除完整代码及实例二叉排序树的查找效率 二叉排序树的定义 二叉排序树（Binary Sort Tree， BST），也称二叉查找树。 二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树： 1） 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字值； 2） 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字值； 3） 左、右子树本身也分别是一棵二叉排序树。 由定义可知，二叉排序树是一个递归的数据结构，可以方便的使用递归算法对二叉排序树进行各种运算。 根据二叉树的定义，可得左子树结点值 ＜ 根结点值 ＜ 右子树结点值。 所以，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。 二叉排序树的结点定义： 二叉树结点的创建： 二叉排序树的查找 二叉排序树的查找是从根结点开始的，沿某个分支逐层向下进行比较的过程。 其查找过程描述如下：若二叉排序树非空，则将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找；否则在根结点的右子树中查找。 实现代码： 二叉排序树的插入 二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入的。 由于二叉排序树是递归定义的，因此插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字＜根结点关键字，则插入左子树，若关键字＞根结点关键字，则插入右子树。 实现代码： 
二叉排序树的构造 构造一棵二叉排序树就是依次输入数据素，并将它们插入二叉排序树中适当位置上的过程。 构造二叉排序树的过程：每读入一个素，就建立一个新结点，若二叉排序树为空，则将新结点作为二叉排序树的根结点；若二叉排序树非空，则将新结点的值与根结点的值比较，若小于根结点的值，则插入左子树，否则插入右子树。 实现代码： 二叉排序树的删除 在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下来，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质（左子树结点值＜根结点值＜右子树结点值）不会丢失。 删除操作一般会出现三种情况： 1） 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。 2） 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。 3） 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。 注：已知二叉排序树经过中序遍历可以得到一个递增的有序序列，这里的直接后继（或直接前驱）应该是指被删除结点在这个中序遍历序列中的直接后继（或直接前驱）。 体现在二叉排序树的图中: 某个结点的直接后继为以该结点为根的右子树中最左下位置的结点，即右子树的最小值； 某个结点的直接前驱为以该结点为根的左子树中最右下位置的结点，即左子树的最大值。 下面依次给出以上三种情况的实例及删除操作： <1> 被删除结点是叶结点，如删除关键字为23的叶子结点。 
<2.1>被删除结点z只有一棵左子树，删除关键字为45的结点。 
<2.2>被删除结点z只有一棵右子树，如删除关键字为78的结点。 
<3>被删除结点z有左、右两棵子树，如删除结点78。 再强调一下寻找替代被删除结点的结点的原则以供结合下图思考： 已知二叉排序树经过中序遍历可以得到一个递增的有序序列，这里的直接后继（或直接前驱）应该是指被删除结点在这个中序遍历序列中的直接后继（或直接前驱）。 体现在二叉排序树的图中: 某个结点的直接后继为以该结点为根的右子树中最左下位置的结点，即右子树的最小值； 某个结点的直接前驱为以该结点为根的左子树中最右下位置的结点，即左子树的最大值。 
实现代码： 对于未执行while循环的情况，如下图示例。 即未执行while循环的的情况为以被删除结点的右子树为根的树没有左子树只有右子树，也就是说，该右子树的最小值即为该根结点的值。 
此外，在上面的代码中，在情况3中选择的是用被删除结点z的直接后继替代z，当然也可以用被删除结点z的直接前驱来替代，那么则需要修改为如下的代码即可。 完整代码及实例 构建的二叉排序树如下图所示，删除时为删除结点78. 运行结果为： 
二叉排序树的查找效率 二叉排序树查找算法的平均查找长度，主要取决于树的高度，即与二叉树的形态有关。 查找成功的平均查找长度为： Σ(本层高度*本层结点个数) / 结点总数 查找不成功的平均查找长度为： Σ(本层高度*本层补上的叶子结点个数) / 补上的叶子总数 如图所示的二叉排序树： 
查找成功的平均查找长度为：（1*1 + 2*2 + 3*3 + 4*3）/ 9 
查找不成功的平均查找长度：（2*1 + 3*3 + 4*6）/ 10
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/57279.html
