二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(8)

算法9.7 删除二叉排序树中的结点 C/C++ 程序：DeleteBST root, p, f DeleteBST BSTNode* &root, BSTNode* p,1. [ 判断被删结点是否有左子树 ] BSTNode* f 若p- lchild NULL BSTNode* r;则 若 f NULL [ 被删结点是否为根结点 ] if p- lchild NULL // *p无左子树则root ← p- rchild; 算法结束 if f NULL否则 若f- lchild p root p- rchild; return; 则f- lchild ← p- rchild; else if f- lchild p算法结束 f- lchild p- rchild; return; 否则f- rchild ← p- rchild; else算法结束 f- rchild p- rchild; return;否则r ← p- lchild else // *p有左子树2. [ 找左子树的“最右下”结点 ] r p- lchild; 循环 当r- rchild ≠ NULL时，执行 while r- rchild ! NULL r ← r- rchild r r- rchild;3. [ 欲删结点的右子树作为*r的右子树 ] // 以下是按方法?，通过调整指针进行删除r- rchild ← p- rchild r- rchild p - rchild;4. [ 欲删结点的左子树的根代替欲删结点 ] if f NULL若f NULL root p- lchild;则root ← p- lchild else if f- lchild p否则 若f- lchild p f- lchild p- lchild; 则 f- lchild ← p- lchild else否则f- rchild ← p- lchild f- rchild p- lchild;5. [ 算法结束 ] ▌ 该算法存在的问题是删除结点后会使树的形状变坏，即会增加二叉排序树的的高度。

这就使得查找时比较次数增多，即查找算法的性能下降。因此，更为实用的方法是按方法?、?' 的规定所进行的二叉排序树的结点删除算法。这里通过两个算法的对比，不仅在算法方面得到较多的训练，而且也可以对删除这个问题有更清楚地了解与掌握。至此，我们已经讲述了查找、插入和删除三种算法。从算法中容易分析出：它们的时间代价都不会超过二叉排序树的深度。特别是插入和删除算法，在二叉排序树中插入和删除结点只需通过调整相关结点的链接指针，而不必像顺序表那样需要大量的结点移动。本节的后续部分还要对二叉排序树的查找效率做进一步的分析，可导出形状更好的二叉排序树，这种二叉排序树具有最佳的查找效率。9.3.2 最佳二叉排序树同一关键字集合，其关键字插入二叉排序树的次序不同，就会构成不同的二叉排序树。例9.6 对于例4中给出的关键字集合 45, 12, 90, 03, 37, 52, 24, 78, 100, 61 ，若按照关键字在此序列中从前向后的顺序逐个插入到二叉排序树中，就生成了一棵如图9-8 a 所示的二叉排序树。若按照关键字在此序列中从后向前的顺序逐个插入到二叉排序树中，就生成了如图9-8 b 所示的另一棵二叉排序树。

对于含有n个关键字的集合，其中的关键字可以有n! 种不同的排列法，因此可以构成n! 棵二叉排序树，虽然其中有些是相同的，但不同的还是大量的 请读者思考不同的二叉排序树应该有多少棵呢? 。对于同一个关键字的集合可以生成如此众多的不同的二叉排序树，那么如何评价它们？也就是说，什么形状的二叉排序树比较好？这可以用查找效率来衡量。为讨论查找效率，需要用到扩充二叉树。扩充二叉树的概念我们在5.6.1和9.2.2小节讲述Huffman树和折半查找所对应的二叉判定树时已经讨论过了。例如，图9-9表示的是图9-8 a 中的二叉排序树所对应的扩充二叉树。下面回顾一下已讲过的内容：在扩充的二叉树中，原来二叉排序树的结点称为内部结点，而新添加的叶结点 图中的方框结点 称为外部结点。在扩充二叉树中，不存在度为1的结点。外部结点的个数等于内部结点的个数加1。每个外部结点均代表着一个可能的关键字集合 如图9-9中，外部结点A表示大于24且小于37的可能关键字集合 。在查找的过程中，如果经比较后落入外部结点所表示的集合时，则一定是查找失败的情况，并且该外部结点的层数就等于该次失败查找的比较次数。而对于成功的查找的比较次数就等于与之相等的那个内部结点所在的层数加1。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-8.html