04级第6章树C.pptVIP

第6章 树和二叉树（Tree Binary Tree） 6.3 遍历二叉树和线索二叉树 6.3.2 线索二叉树 讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？ 为区别两种不同情况，特增加两个标志域： 1. 有关线索二叉树的几个术语： 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 例1：画出以下二叉树对应的中序线索二叉树。 例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成算法（递归算法见教材P134-135） 3. 线索二叉树的遍历（无需堆栈） 附：中序线索二叉树遍历步骤 （算法6.5）： 算法流程： 6.4 树和森林 6.4.1 树和森林与二叉树的转换 树转二叉树举例： 讨论2：二叉树怎样还原为树？ 森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树） 讨论4：二叉树如何还原为森林？ 6.4.2 树和森林的存储方式 例如： 6.4.3 树和森林的遍历 森林的遍历 附：二叉树若干典型算法（习题课） 附2：层次遍历算法(需要利用队列) 严题集6.47 ④ 附3：判别给定二叉树是否为完全二叉树 严题集6.49 ④ 附4：中序遍历的非递归算法(或称迭代算法)见教材P131 讨论：若采用“先转换，后遍历”方式，结果是否相同？ 例如： A B C D E F G H J I 先根序列： 中根序列： A B C D E F G H I J B C D A F E H J I G A B C D E F G H J I 先序序列： 中序序列： A B C D E F G H I J B C D A F E H J I G 结论：森林的先根和中根遍历在两种方式下的结果相同。 但森林的后根遍历则不一定，因而少用 2. 如何按层次输出二叉树中所有结点？ 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，此时绝不能用递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。 1. 如何求二叉树的深度，或从某个结点开始的子树深度？ 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 A B C D E 算法见附1 算法见附2 算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈(迭代方式) 。可直接用while语句和push/pop操作。参见教材P130-131程序。 4 中序遍历的非递归算法如何实现？ 3.如何判别给定二叉树是否为完全二叉树？ 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层次遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层次遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。 算法见附3 算法见附4 Void ABC(Bitree p, int l, int h) { if p≠NIL then { l=l+1; if lh then h=l; ABC(p-Lchild, l, h); ABC(p-Rchild, l, h); } } 法1：从根开始向下计算层次(比从叶子往上计算更简单) l、h分别表示二叉树的层次数和深度。 想一想，l和h的初始值应设为多少？ 开始调用时，应当用ABC（p, 0, 0） 若去掉h形参中的“”号，则h不变化，算出的更深层数不能正确返回, h将永远为 0。 附1：求二叉树的深度的算法 严题集6.44 ④ int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针 { int leftdep, rightdep; //设左右两个深度/层次计数器 if(BT==NULL) return(0); //当前结点指针为空则立即返回 else { leftdep= BTreeDepth(BT-left); //遍历当前结点左子树 rightdep=BTreeDepth(BT-right); //遍历当前结点右子树 if( leftdeprightdep)return(leftdep+1); //从叶子起计数 else return(rightdep+1); } } //BTreeDepth 法2：递归时从叶子开始向上计数，层深者保留。 void LayerOrder(Bitree T) //层序遍历二叉树 { InitQ