详解二叉排序树 二叉排序树的插入、查找、删除 二叉排序树的定义 二叉排序树右称二叉查找树。或者为空树，或者是具有以下性质： （1）若它的左子树不为空，则左子树所有节点的值小于根结点， （2）若它的右子树不为空，则根结点的值小于所有右子树结点的值 （3）它的左右子树叶分别为二叉排序树 总结起来就是根据结点的值有：左子树<根结点<右子树 如下图就是一棵二叉排序树 
它的中序遍历：12、19、23、28、34、36、38、42、53、65、90，刚好是排好序的。 二叉排序树的查找分析 二叉排序树有一些基本的应用，可以用于查找，查找的长度与树的深度有关。其平均查找长度为logN（以2位底的对数，N为结点个数）。 一个序列的排序二叉树有多种构造情况。下面考虑两种极端情况：深度最小和深度最大的二叉排序树。 关键字序列（45,24,53,12,37,93），假设6个记录的查找概率相等都为1/6 
容易看出这是一棵完全二叉树，该数的深度（最大层次）为3，它的平均查找长度为： ASL = 1/6（1+2+2+3+3+3）= 14/6 再来看该关键字序列构成深度最大的二叉排序树 
这是一棵单支树，其深度为6，它的平均查找长度为： ASL = 1/6（1+2+3+4+5+6）= 21/6 在随机情况下,该数的平均查找长度总是介于这两种情况之间，即14/6 < log6 < 21/6。二叉排序树的平均查找长度和logN是等数量级的。 二叉排序树的构造过程 以上述完全叉树序列为例，构造该二叉排序数的过程如下图： 
容易看出，每次插入新的结点都是二叉排序树上的叶子结点，则在插入时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。 结点的插入操作与二叉排序树的定义紧密相关，即左<根<右，新插入一个关键字时，从根结点开始比较，直到找到合适的插入位置为止。还有一种情况就是一个序列中可能有两个相同的关键字，对于这种情况，向树中插入关键字时遇到相同关键字时，什么都不做，不进行重复插入操作。 二叉排序树的删除过程 删除二叉排序树中任意一个结点，需要分成以下三种情况讨论： （1）删除的是叶子结点 这种情况最简单，由于删除叶子结点不会破坏整棵树的结构，只需要修改其双亲结点的指针即可。 （2）删除的结点只有左子树或只有右子树。 这种情况只需要将其左子树或右子树往上推，替代要删除结点的位置，显然，作此修改也不会破坏二叉排序树的结构。 （3）删除的结点左右子树都不为空 这种情况稍微复杂一点，为了不保持二叉排序树的结构，有两种思路，一种就是从要删除结点的左子树中选取最大的结点进行替代之，另一种就是从要删除的结点的右子树中选取最小的结点替代之。 下面考虑第三种情况 
f、p、q、s分别为指向结点F、P、Q、S的指针，假如现要删除结点P，它的左右子树都不为空。 其一就是寻找P的左子树中的最大结点，代替之。 易知左子树中最大结点为S，将P结点用S结点代替，还需处理S结点的左孩子K，由于S只有左子树K,在删除结点S之后，只要令K为S的双亲Q的右子树即可。 其二就是寻找P结点的右子树中最小的结点，代替之。 找到P后，第一步就是往右走一步到R，若R的左子树不为空，则最小的结点在R的左子树中，只需一直往左走即p=p->Left,指定p->Left为空（右子树最小结点，其左子树定为空 ），则找到最小结点，将其代替要删除的结点P，并将最小结点的右子树代替该最小结点即可。如下图，Z为要删除结点中右子树中最小结点，将P用Z代替后，Z的位置再由Y代替 
若R的左子树为空，那么最小结点就是R，只需将R往上推代替P 
具体实现：
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/34216.html
