8.3.1 二叉排序树 返回目录： Chilan Yu：《数据结构》目录链接 1. 二叉排序树定义与描述 二叉排序树（二叉查找树），它是一种特殊结构的二叉树。 其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值均大于（或大于等于）根结点的值； （3）它的左右子树也分别为二叉排序树 由定义可以得出二叉排序树的一个重要性质：中序遍历一个二叉排序树时可以得到一个递增有序序列。 2. 二叉排序树的插入与创建 （1）二叉排序树的插入 【算法思想】 已知一个关键字值为Key的结点s，插入的方法： ①若二叉排序树是空树，则Key 成为二叉排序树的根； ②若二叉树排序树非空，则将key与二叉树排序树的根进行比较： a. 如果key的值等于根结点的值，则停止插入。 b. 如果key的值小于根结点的值，则将key插入左子树。 c. 如果key的值大于根结点的值，则将key插入右子树。 二叉排序树的插入算法的时间复杂度是
（2）创建二叉排序树 【算法思想】 首先，将二叉排序树初始化为一棵空树，然后逐个读入素，每读入一个素，就建立一个新的结点，并插入到当前已生成的二叉排序树中，即通过多次调用二叉排序树的插入新结点的算法实现，注意插入时比较结点的顺序始终是从二叉排序树的根结点开始。 二叉排序树的插入与创建小结 3. 二叉排序树的查找 【算法思想】 首先将待查关键字key与根结点关键字t进行比较，如果： （1）k=t：则返回根结点地址；（2）k<t：则进一步查左子树； （3）k>t：则进一步查右子树。 （1）二叉排序树查找的递归算法 其中用Layer计层数。 （2）二叉排序树查找的非递归算法 其中用Layer计层数。 小结 二叉排序树的查找完整代码： 4. 二叉排序树的删除 从二叉排序树中删除一个结点，必须保证删除后所得的二叉树仍然满足二叉排序树的性质不变。 【算法思想】 首先确定被删除的结点是否在二叉排序树中。若不在 ，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似）。 下面分三种情况讨论： （1）若p为叶结点，则可直接将其删除： （2）若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树。即： （3）若p既有左子树，又有右子树， 如下图(a)，则处理的方法有两种：
方法一：首先找到p结点在中序序列中的直接前驱s结点，如图 (b) 所示，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：结果如图 (c) 所示。
方法二：首先找到p结点在中序序列中的直接前驱s结点，如图 (b) 所示，然后用s结点的值，替代p结点的值，再将s结点删除，原s结点的左子树改为s的双亲结点q的右子树：结果如图 (d) 所示。
小结 二叉排序树的删除完整代码： 5. 二叉排序树的特性 对于二叉排序树，若中序遍历，则可以得到一个递增有序序列。 若逆中序遍历（RDL），则可以得到一个递减有序序列。 返回目录： Chilan Yu：《数据结构》目录链接
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/85712.html
