77树与二叉树的转换 孩子兄弟 表示法 讨论1:树如何转为二叉树? 转换步骤 step1:将树中同一结点的兄弟相连; 加线 step2:保留结点的最左孩子连线, 删除其它孩子连线; 抹线 step3:将同一孩子的连线绕左孩子 旋转45度角。 旋转
1 7.7 树与二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟 表示法 step2: 保留结点的最左孩子连线， 删除其它孩子连线； step3: 将同一孩子的连线绕左孩子 旋转45度角
树转二叉树举例 方法:加线抹线旋转 特点是? 根结点没有右孩子! 兄弟相连 长兄为父孩子靠左 b d d g f)(
2 方法：加线—抹线—旋转 a b e i d f g h c 树转二叉树举例： a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！
讨论2:二叉树怎样还原为树? 要点:逆操作,把所有右孩子变为兄弟! b (d) d g g h
3 讨论2：二叉树怎样还原为树？ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f g h c i
讨论3:森林如何转为二叉树? 即F={TT2,…,Tm}={ root, LB,RB} 法一 ①各森林先各自转为二叉树; ②依次连到前一个二叉树的右子树上 法二:森林直接变兄弟,再转为二叉树 (参见教材P138图6.17,两种方法都有转换示意图) 法一和法二得到的二叉树是完 全相同的、惟一的
4 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 讨论3：森林如何转为二叉树？ 即F={T1 , T2 , …,Tm} B={root, LB, RB} 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完 全相同的、惟一的
森林转二叉树举例: 用法二,森林直接变兄弟,再转为二叉树) )D(F)(田 兄弟相连长兄为父① 头树为根孩子靠左
5 A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 森林转二叉树举例： （用法二，森林直接变兄弟，再转为二叉树） 兄弟相连 长兄为父 头树为根 孩子靠左 A
讨论4:二叉树如何还原为森林? 即B={ root, lB,RBy={T1,T2…Tm} 要点:把最右边的子树变为森林,其余右子树变为兄弟
6 A B C D E F G H J I 讨论4：二叉树如何还原为森林？ 要点：把最右边的子树变为森林，其余右子树变为兄弟 即B={root, LB, RB} F={T1 , T2 , …,Tm} A B C D E F G H J I E F A B C D G H J I
7.8树的遍历 深度优先遍历(先根、后根)树没有中序遍历(因 树的遍历 子树不分左右) 广度优先遍历(层次) 先根遍历 后根遍历 访问根结点; 按照从左到右依次后根遍 按照从左到右依次先根遍 历根结点的每棵子树 历根结点的每棵子树。>访问根结点。 例如 先根序列: a bc de b 后根序列: baca d
7 7.8 树的遍历 树的遍历 例如： a b d c e 先根序列： 后根序列： a b c d e b d c e a 深度优先遍历（先根、后根） 广度优先遍历（层次） 先根遍历 访问根结点； 按照从左到右依次先根遍 历根结点的每棵子树。 • 后根遍历 ➢ 按照从左到右依次后根遍 历根结点的每棵子树； ➢ 访问根结点。 树没有中序遍历（因 子树不分左右）
讨论:树若采用“先转换,后遍历”方式,结果是否一样 先序遍历: a bc de 中序遍历: baca 后序遍历: dec b a d 树的先根序列: a bcde 结论: 树的后根序列: baca 1.树的先根遍历与二叉树的先序遍历相同 2树的后根遍历相当二叉树的中序遍历; 3.树没有中序遍历,因为子树无左右之分
8 讨论：树若采用“先转换，后遍历”方式，结果是否一样？ a b d e c 先序遍历： 后序遍历： 中序遍历： d e c b a a b d c e a b c d e b d c e a 1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。 结论： 树的先根序列：a b c d e 树的后根序列：b d c e a
附1:求二叉树的深度的算法 法1:从根开始向下计算层次比从叶子往上计算更简单) Void ABC(Bitree p, int int &h) ifp≠ NIL then h分别表示二叉树的层次 数和深度 l=+1; 想一想,l和h的初始值应设 if>h then h =: 为多少? 开始调用时,应当用ABC ABC(p->Lchild, I, h); (p,0,0) AbC(p->Rchild, I,h); 若去掉h形参中的“&”号,则h不 变化,算出的更深层数不能正确 返回,h将永远为0
9 Void ABC(Bitree p, int l, int &h) { if p≠NIL then { l=l+1; if l>h 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：求二叉树的深度的算法
法2:递归时从叶子开始向上计数,层深者保留。 int BTreeDepth( Btree*BT)∥BT为二叉树某结点的指针 { int leftdep, righter;∥设左右两个深度/层次计数器 if(BT=NULI) return(0);∥当前结点指针为空则立即返回 else { leftie= BTreeDepth(BT->left);/遍历当前结点左子树 righter= BTreeDepth( BT->right);/遍历当前结点右子树 if( efter> righter) return( efter+);/从叶子起计数 else return(rightdep+1); )//BTreeDepth
10 int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针 { int leftdep, rightdep; //设左右两个深度/层次计数器 if(BT==NULL) return(0); //当前结点指针为空则立即返回 else { leftdep= BTreeDepth(BT->left); //遍历当前结点左子树 rightdep=BTreeDepth(BT->right); //遍历当前结点右子树 if( leftdep>rightdep)return(leftdep+1); //从叶子起计数 else return(rightdep+1); } } //BTreeDepth 法2：递归时从叶子开始向上计数，层深者保留