数据结构课件chp5.pptVIP

概述 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 二叉查找树 选择树 树与森林 (Tree Forest) 二叉树的计数 在二叉查找树上查找 如何在二叉查找树上检索给定的值？（限定二叉查找树上任何两个结点均不相同）（1）若二叉查找树为空，查找失败。（2）首先用给定的值和根结点的值进行比较，若相等，则查找成功。（3）若给定的值比根结点的值小，则转根结点的左子树进行查找。（4）若给定的值比根结点的值大，则转根结点的右子树进行查找。 在二叉查找树上查找 递归查找 迭代查找 通过排序查找 向二叉查找树插入结点 向二叉查找树中插入新结点必须保证插入新结点后，二叉树仍然满足二叉查找树的定义。 如何在二叉查找树中插入新结点？（1）若二叉查找树为空，则新结点应作为二叉查找树的根结点。（2）将新结点的值和根结点的值比较，如果相等返回。（此时要插入的结点在树中已存在）（3）如果新结点的值小于根结点的值，则转二叉查找树的左子树继续插入操作。（4）如果新结点的值大于根结点的值，则转二叉查找树的右子树继续插入操作。 向二叉查找树插入结点 依次向一棵空的二叉查找树插入下面的关键字：e、b、d、f、a、g 和 c。 从二叉查找树上删除结点 从二叉查找树上删除结点应保证结点删除后得到的二叉树仍然是二叉查找树。 如何从二叉查找树中删除结点？（1）如果要删除的结点是叶子结点，直接删除并更新父结点指针。（2）如果要删除的结点只有一棵非空子树，则令该非空子树代替被删除的结点作为被删除结点父结点的相应子树。（3）如果要删除的结点的两棵子树均非空，问题比较复杂，此时用要删除结点的中序前趋替换要删除的结点，再运用（1）和(2)中的方法删除处在原来位置上的要删除结点的中序前趋。（或中序后继） 一个结点的中序前趋有什么特点？如何找一个结点的中序前趋？（或中序后继） 从二叉查找树上删除结点 二叉查找树的查找效率 不同的插入顺序导致不同的二叉查找树。例如，按照下列顺序插入构造二叉查找树（1）d、b、a、c、f、e和g（2）a、b、c、d、e、f和g 当插入的结点顺序排列时，二叉查找树蜕变成一棵单链树。 在一棵完全平衡的二叉查找树上成功查找一个结点比较次数最多为 在一棵单链树中成功查找一个结点最多比较次数为n。 二叉查找树的优点和缺点 优点（1）二叉查找树查找效率高于一般顺序表的查找效率。尤其二叉查找树是比较平衡的二叉查找树时如此。（2）二叉查找树为链式存储，插入和删除无需移动大量结点。 缺点（1）由于插入结点的顺序常常无法准确预测，构造出的二叉查找树通常不是平衡的二叉查找树。 需要一种方法保持二叉查找树的平衡性。 顺串是记录的有限序列，且这些记录按关键字的非递减顺序排列。 假设需要将k个顺串归并为一个，这可通过反复输出关键字最小的记录完成。 最小关键字可能在k个顺串的前端记录的任何一个之中，因此需要从k种可能中选出最小。最直接的方法是作k – 1次比较。但对于k 2，如果利用上一次比较获得的知识，就可以使本次及以后比较的次数减少。 选择树就是一种能够记载上一次比较获得的知识的数据结构。选择树是一棵完全二叉树，有胜者树和败者树两种。 选择树 (P213) 4.6.1 胜者树 胜者树的构造与锦标赛类似，胜者是关键字较小的记录。每个非叶结点表示比赛的胜者，根结点表示总胜者，即树中关键字最小的结点。 作为完全树，胜者树可用顺序方法表示。每个叶结点表示相应顺串的第一个记录。 由于记录一般较大，每个结点实际存放的是其所表示记录的缓冲区下标。 设buf[i]存放顺串i（0≤i k）的第一个记录，则buf[i]对应的叶结点编号是k + i，这意味着叶结点存放的下标可推算得到，不必用空间存储。 下图是一棵k = 8的胜者树： 其中，每个结点旁的数字是该结点的顺序编号。虽然每个非叶结点实际存放胜者记录下标，但为便于直观比较，图中也给出了胜者的关键字。叶结点直接用buf[i]代替。 由根结点指向的记录（buf[3]）的关键字最小，可输出。顺串3的下一个记录进入buf[3]，其关键字为15。为了重构胜者树，需要沿buf[3]对应的叶结点到根结点进行一系列比赛。 结点10和11比赛的胜者又是结点11（15 20），结点4和5比赛的胜者是结点4（9 15），结点2和3比赛的胜者是结点3（8 9）。 新的胜者树如下图： 其中，粗体字结点是发生了变化的结点。可见，