《树二叉树树森林与二叉树的转换树的应用》由会员分享，可在线阅读，更多相关《树二叉树树森林与二叉树的转换树的应用（57页珍藏版）》请在金锄头文库上搜索。
1、树树二叉树二叉树树、森林与二叉树的转换树、森林与二叉树的转换树的应用树的应用第五章第五章 树和二叉树树和二叉树梯俊枕隶枚樱炬儿吉棱双亩考萧欣泡霞耍么糊三壶桔箍妄诛梗县蛋溶闭府树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20241树和森林的概念树和森林的概念树的定义树的定义树的定义树的定义 树是由树是由树是由树是由n n ( (n n 0) 0)个结点组成的有限集合。如果个结点组成的有限集合。如果个结点组成的有限集合。如果个结点组成的有限集合。如果n n = 0= 0，称为空树；如果，称为空树；如果，称为空树；如果，称为空树；如果n n 0 0，则，则，则，
2、则 有一个特定的称之为有一个特定的称之为有一个特定的称之为有一个特定的称之为根根根根(root)(root)的结点，它只有的结点，它只有的结点，它只有的结点，它只有直接后继，但没有直接前驱；直接后继，但没有直接前驱；直接后继，但没有直接前驱；直接后继，但没有直接前驱； 除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为mm ( (mm 0) 0)个互不相个互不相个互不相个互不相交的有限集合交的有限集合交的有限集合交的有限集合T T0 0, , T T1 1, , , , T Tmm-1-1，每个集合又是一棵树，每个集合又是一棵树，每个集合又是一棵树
3、，每个集合又是一棵树，并且称之为根的并且称之为根的并且称之为根的并且称之为根的子树子树子树子树(subTree)(subTree)。每棵子树的根结点。每棵子树的根结点。每棵子树的根结点。每棵子树的根结点有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有0 0个或多个直接后个或多个直接后个或多个直接后个或多个直接后继。继。继。继。朔供悲陋亚斥邑娱蔡碉锯犁锚泳擒支潍供刊贺膨组摘陀伙谱琅晓严蛆寒拇树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20242树的表示树的表示树的表示树的表示 树型表示树
4、型表示树型表示树型表示bacghdefij攀菊绪户捉焙链宏李路蹈要弄侮煞雪陵缓歧拿吴芯摘氏方赫拽偶枪变断伶树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20243凹入表表示凹入表表示凹入表表示凹入表表示abdeijfcgh醋堆皆周年馏撮刀捡吻鞋岩饵蛰捻灿史邯湃鱼绪辩迢披盂泼敖除蛙侥染粹树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20244嵌套集合表示嵌套集合表示嵌套集合表示嵌套集合表示嵌套括号表示嵌套括号表示嵌套括号表示嵌套括号表示ijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) )
5、 )条阁膜梭支囚畅泄咙熙光琶痘决逞承辛鳖踢吗蔗岿滩虞些哲频垄攫痰书纤树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20245 结点结点结点结点(node)(node)(node)(node) 结点的度结点的度结点的度结点的度(degree) (degree) (degree) (degree) 结点的子树个数结点的子树个数结点的子树个数结点的子树个数 分支分支分支分支(branch)(branch)(branch)(branch)结点结点结点结点 度不为度不为度不为度不为0 0 0 0的结点的结点的结点的结点 叶叶叶叶(leaf)(leaf)(leaf)(l
6、eaf)结点结点结点结点 度为度为度为度为0 0 0 0的结点的结点的结点的结点 子女子女子女子女(child)(child)(child)(child)结点结点结点结点 某结点子树的根结点某结点子树的根结点某结点子树的根结点某结点子树的根结点 双亲双亲双亲双亲(parent)(parent)(parent)(parent)结点结点结点结点 某个结点是其子树之根的某个结点是其子树之根的某个结点是其子树之根的某个结点是其子树之根的 双亲双亲双亲双亲 垄甄届况吩夹藤衅韭遍材赡礁后瓶侥倦绝俘吠吝框澈欢顺酋存胆驹廓叛抉树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/2
7、0246 兄弟兄弟兄弟兄弟(sibling)(sibling)(sibling)(sibling)结点结点结点结点 具有同一双亲的所有结点具有同一双亲的所有结点具有同一双亲的所有结点具有同一双亲的所有结点 祖先祖先祖先祖先(ancestor)(ancestor)(ancestor)(ancestor)结点结点结点结点 若树中结点若树中结点若树中结点若树中结点k k k k到到到到k k k ks s s s存在一条路径，存在一条路径，存在一条路径，存在一条路径， 则称则称则称则称k k k k是是是是k k k ks s s s的祖先的祖先的祖先的祖先 子孙子孙子孙子孙(descendant)
8、(descendant)(descendant)(descendant)结点结点结点结点 若树中结点若树中结点若树中结点若树中结点k k k k到到到到k k k ks s s s存在一条路径，存在一条路径，存在一条路径，存在一条路径， 则称则称则称则称k k k ks s s s是是是是k k k k的子孙的子孙的子孙的子孙 结点所处层次结点所处层次结点所处层次结点所处层次(level) (level) (level) (level) 根结点的层数为根结点的层数为根结点的层数为根结点的层数为1 1 1 1，其余结点的层，其余结点的层，其余结点的层，其余结点的层 数为双亲结点的层数加数为双亲结
9、点的层数加数为双亲结点的层数加数为双亲结点的层数加1 1 1 1 树的高度树的高度树的高度树的高度(depth) (depth) (depth) (depth) 树中结点的最大层数树中结点的最大层数树中结点的最大层数树中结点的最大层数 树的度树的度树的度树的度(degree)(degree)(degree)(degree)n n 有序树有序树有序树有序树 子树的次序不能互换子树的次序不能互换子树的次序不能互换子树的次序不能互换n n 无序树无序树无序树无序树 子树的次序可以互换子树的次序可以互换子树的次序可以互换子树的次序可以互换n n 森林森林森林森林 互不相交的树的集合互不相交的树的集合互
10、不相交的树的集合互不相交的树的集合板领酪焚亲陨拢垦絮咆宾秉啼电祸蔽初柑瑰源盆骂眺伎互伍升惊趟翅舅坚树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20247树的基本操作树的基本操作1 1、初始化、初始化、初始化、初始化2 2、求指定结点所在树的根结点、求指定结点所在树的根结点、求指定结点所在树的根结点、求指定结点所在树的根结点3 3、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点4 4、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点5 5、求指定结点的最右边兄弟结点
11、、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点6 6、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它 的子树的子树的子树的子树7 7、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结点的某一子树8 8、树的遍历、树的遍历、树的遍历、树的遍历蜕悲绳房迭犀笨扳啪免讨扑躺涕华绍锐秀位凿慌纹台缎秉拆蚂幢幼恋蝗饱树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20248二叉树二叉树 (Bi
12、nary Tree)二叉树的定义二叉树的定义二叉树的五种不同形态二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该集合一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。为左子树和右子树的、互不相交的二叉树组成。给调跪改墩狡祖姬证仿褪很珊栖譬睁加十茨钻撞驼犁匙沽迪浸撮恃稽回效树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/20249性质性质性质性质1 1 若二叉树的层次从若二叉树的层次从若二叉树的层次从若二叉树的层次从1 1开始开始开始开始,
13、, 则在二叉树的则在二叉树的则在二叉树的则在二叉树的 第第第第 i i 层最多有层最多有层最多有层最多有 2 2i-1 i-1 个结点。个结点。个结点。个结点。( (i i 0) 0)二叉树的性质二叉树的性质证明：证明：证明：证明：i = 1 i = 1 时，有时，有时，有时，有2 2i-1 i-1 = = 2 20 0 =1 =1，成立，成立，成立，成立假定假定假定假定 ：i = k i = k 时性质成立；时性质成立；时性质成立；时性质成立；当当当当 i = k+1 i = k+1 时，第时，第时，第时，第k+1k+1的结点至多是第的结点至多是第的结点至多是第的结点至多是第k k层结点层结
14、点层结点层结点的两倍，即总的结点个数至多为的两倍，即总的结点个数至多为的两倍，即总的结点个数至多为的两倍，即总的结点个数至多为2222k-1 k-1 = = 2 2k k故命题成立故命题成立故命题成立故命题成立瑶盯畏褂凭信壁舔涎笺付缝齐遏瘸卡趁帝捆伐豆腕湘刀帛掳伴屹狭曼忱月树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202410性质性质性质性质2 2 高度为高度为高度为高度为k k的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有 2 2k k-1-1个结点。个结点。个结点。个结点。 ( (k k 1) 1)证明：仅当每一层都含有最大结点数时，二叉树
15、证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质的结点数最多，利用性质的结点数最多，利用性质的结点数最多，利用性质1 1可得二叉树的结点数可得二叉树的结点数可得二叉树的结点数可得二叉树的结点数至多为：至多为：至多为：至多为：2 20 0 + + 2 21 1 + + 2 22 2 + + 2 23 3 + + + + 2 2k-1 k-1 = = 2 2k k 1 1 名堰政膏缉滤掠渡梁抢只趁裹司剃富害腰湖撇池滚醛靴迟货元纬姨历荐沼树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换
16、树的应用7/27/202411性质性质性质性质3 3 对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树, , 如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为 n n0 0, , 度为度为度为度为2 2的非叶结点个数为的非叶结点个数为的非叶结点个数为的非叶结点个数为 n n2 2, , 则有则有则有则有 n n0 0n n2 21 1证明：证明：证明：证明：1 1、结点总数为度为、结点总数为度为、结点总数为度为、结点总数为度为0 0的结点加上度为的结点加上度为的结点加上度为的结点加上度为1 1的结点再加上度的结点再加上度的结点再加上度的结点再加上度 为为
17、为为2 2的结点：的结点：的结点：的结点： n = n n = n0 0 + n + n1 1 + n + n2 22 2、另一方面，二叉树中一度结点有一个孩子，二、另一方面，二叉树中一度结点有一个孩子，二、另一方面，二叉树中一度结点有一个孩子，二、另一方面，二叉树中一度结点有一个孩子，二 度结度结度结度结 点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此， 结点总数为：结点总数为：结点总数为：结点总数为： n = n n = n1 1 + 2n + 2n2 2
18、 + 1+ 13 3、两式相减，得到：、两式相减，得到：、两式相减，得到：、两式相减，得到： n n0 0 = n = n2 2 + 1 + 1 硬放滩端唐鼓北委帝脯木刊慧挫琴冶摄比铀锦溜沸遗垛坦锈祟闭啸川陈要树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202412定义定义1 满二叉树满二叉树(Full Binary Tree) 一棵深度为一棵深度为k 且有且有2k-1个结点的二叉树。个结点的二叉树。定义定义2 完全二叉树完全二叉树(Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h+1层。层。除第除第h层
19、外，其它各层层外，其它各层(0 h-1)的结点数都达的结点数都达到最大个数，第到最大个数，第h层从右向左连续缺若干结层从右向左连续缺若干结点，这就是完全二叉树。点，这就是完全二叉树。藻嫁漏骆己迄镁表树烟投步脑笑堑诸脚芝镣吸虽彦个次嫁及乃肉省调呵氮树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202413性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度 为为 log2n + +1证明：设完全二叉树的高度为证明：设完全二叉树的高度为h h，则有，则有 2 2h-1h-1 - 1 - 1 n n 2 2h h - 1 - 1 2 2h-1h-
20、1 = = n n 2 2h h 取对数取对数 h h 1 log 1 log2 2( (n n) ) 1, 1, 则则则则 i i 的双亲为的双亲为的双亲为的双亲为 i i /2/2 n n 若若若若2*2*i i = n n/2/2 的结点必定是页结点的结点必定是页结点的结点必定是页结点的结点必定是页结点 若若若若2*2*i i+1 = +1 data s-datach;ch; s-lchild s-lchildNULL;NULL; s-rchild s-rchildNULL;NULL; 泌胎韵罐意驾潍丝编钞森星钨告刁手心友膳备蛀兄灌忍沽嗓讲棵薪痪幌凝树二叉树树森林与二叉树的转换树的应用树
21、二叉树树森林与二叉树的转换树的应用7/27/202423 rear+; Qrear rear+; Qrears;s; if (rear=1) root if (rear=1) roots;s; else else if (s&Qfront) if (s&Qfront) if (rear%2=0) Qfront-lchild if (rear%2=0) Qfront-lchilds;s; else Qfront-rchild else Qfront-rchilds;s; if (rear%2=1) front+; if (rear%2=1) front+; ch=getchar(); ch=ge
22、tchar(); return root; return root;辩涯贡宿娠粪级法卒捻管观孜汤翠资嘛磐曳攻数肯般沧闯佳邹推拇夸侣砒树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202424中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是： 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L) (L)； 访问根结点访问根结点访问根结点访问根结点 (V) (V)； 中序遍历
23、右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R) (R)。遍历结果遍历结果遍历结果遍历结果 a a + + b b * * c c - - - - d d - - - - e e / / f f中序遍历表达式语法树表达式语法树二叉树的遍历乎孵击哲岂遇峻辈沪绒然池析睛叔遥陛既袄砂坚戎越哨端著床狐匈得鹏逐树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202425中序遍历算法中序遍历算法INORDER(bitree *cnt)INORDER(bitree *cnt) if (cnt) if (cnt) INORDER(t-lch); INORDER(t-l
24、ch); printf( printf(“t%cnt%cn”,t-data);,t-data); INORDER(t-rch); INORDER(t-rch); 毅刮算圭盘豆规然卢个克描钞州倚羌撂山弥尤种孜盼堕仟毫盾牌竿坑拓樱树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202426中序遍历二叉树的递归过程图解中序遍历二叉树的递归过程图解热乘蛋兆猜吭算刽服康账蔷馏泌场排苦正瘦哩勒咙日雏慌霞坟疮验案丝忙树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202427前序遍历前序遍历二叉树算法的框架是前序遍历二叉树算法的框架是前序遍
25、历二叉树算法的框架是前序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 访问根结点访问根结点访问根结点访问根结点 (V) (V)； 前序遍历左子树前序遍历左子树前序遍历左子树前序遍历左子树 (L) (L)； 前序遍历右子树前序遍历右子树前序遍历右子树前序遍历右子树 (R) (R)。遍历结果遍历结果遍历结果遍历结果- - - - + + a a * * b b - - - - c dc d / / e fe f醉毅授耳辽靳艘释鸿哟硒择柯热腹热惕铅六照虎拟牙缓辙畴拌播症骄版捅树二叉树树森林与二叉树的转换树的
26、应用树二叉树树森林与二叉树的转换树的应用7/27/202428后序遍历后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 后序遍历左子树后序遍历左子树后序遍历左子树后序遍历左子树 (L) (L)； 后序遍历右子树后序遍历右子树后序遍历右子树后序遍历右子树 (R) (R)； 访问根结点访问根结点访问根结点访问根结点 (V) (V)。遍历结果遍历结果遍历结果遍历结果a b c da b c d - - - - * + * + e
27、fe f / / - - - -续各众笨欣早恋挨怖迷额历艘辞熔普豪遇茨季乳总铱孺凹哼勾褒墓谷能滩树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202429层序遍历层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则，如队列不空，循环：否则，如队列不空，循环：否则，如队列不空，循环：否则，如队列不空，循环： 根结点入队，并作为当前结点；根结点入队，并作为当前结点；根结点入队，并作为当前结点；根结点入队，并作
28、为当前结点；将当前结点的左右孩子入队；将当前结点的左右孩子入队；将当前结点的左右孩子入队；将当前结点的左右孩子入队； 做出队操作，队首元素作为当做出队操作，队首元素作为当做出队操作，队首元素作为当做出队操作，队首元素作为当 前结点前结点前结点前结点 最后，出队序列就是层序遍历最后，出队序列就是层序遍历最后，出队序列就是层序遍历最后，出队序列就是层序遍历 序列序列序列序列遍历结果遍历结果遍历结果遍历结果- - - - + / + / a a * * e fe f b b - - - - c dc d 哲毕栗哮眯斤骏妥睫檬惺详捌帝播溶筛勉赁栏稠疽埂春雁絮涡涡迅谩委沂树二叉树树森林与二叉树的转换树的
29、应用树二叉树树森林与二叉树的转换树的应用7/27/202430例：在二叉树中查找具有给定值的结点例：在二叉树中查找具有给定值的结点bitree findnode(bitree *t, datatype x)bitree findnode(bitree *t, datatype x) if ( t = NULL) return(NULL); if ( t = NULL) return(NULL); else if ( t-data = x) return(t); else if ( t-data = x) return(t); else return( findnode(t-lchild)| e
30、lse return( findnode(t-lchild)| findnode(t-rchild) ) findnode(t-rchild) ) 糟樊皮掂沟君埠泞获下广耶命映度明主捎宣天片试惦琳掏眺拘烦绚寿儿捻树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202431例：给定一棵二叉树，输出其嵌套括号表示例：给定一棵二叉树，输出其嵌套括号表示void print(bitree *t)void print(bitree *t) if (t) if (t) printf( printf(“%d%d”, t-data);, t-data); if (t-lchi
31、ld |t-rchild) if (t-lchild |t-rchild) printf( printf(“( (”);); printf(lchild); printf(lchild); if (t-rchild) printf( if (t-rchild) printf(“, ,”);); print(rchild); print(rchild); printf( printf(“) )”); ); 蜘虫昌畦啮终甲庶夸楚铺肇英埋指钒御棕疮秋疟摧呼剃锋喧遂有滴窑赔泄树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202432例：求二叉树的深度例：求二叉树的深
32、度void depth(bitree *t)void depth(bitree *t) int dep1, dep2; int dep1, dep2; if (t = = NULL) return(0); if (t = = NULL) return(0); else else dep1 = depth(t-lchild); dep1 = depth(t-lchild); dep2 = depth(t-rchild); dep2 = depth(t-rchild); if (dep1 dep2) return(dep1 + 1); if (dep1 dep2) return(dep1 + 1)
33、; else return(dep2 + 1); else return(dep2 + 1); 挽寺趣曳蹈缕揪浸秽实蓝茅餐蜜辉硷抉运该矾迂焉轿额雕婉必研钾画品兆树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202433例：证明：一棵二叉树的前序序列和中序序列可例：证明：一棵二叉树的前序序列和中序序列可以唯一的确定这棵二叉树。以唯一的确定这棵二叉树。用归纳法证明：用归纳法证明：1、当、当 n = 1时，结论显然成立；时，结论显然成立；2、假定当、假定当 n = k 时，结论成立；时，结论成立；3、当、当 n = k + 1 时，假定前序序列为和中序序列时，假定
34、前序序列为和中序序列分分 别为：别为： a1，am 和和 b1， ，bm 域嘘淳萧龟诸曼岗妆茬苟淀辗尝妨四竖舌拭嘶济疵蒜辗归耪暖限廷因搁腆树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202434 如中序序列中与前序序列如中序序列中与前序序列a1相同的元素为相同的元素为bj。j = 1时，二叉树无左子树，由时，二叉树无左子树，由 a2，am 和和 b2， ，bm 可以唯一的确定二叉树的右子树；可以唯一的确定二叉树的右子树；j = m时，二叉树无右子树，由时，二叉树无右子树，由 a2，am 和和 b1， ，bm-1 可以唯一的确定二叉树的左子树；可以唯一的确定
35、二叉树的左子树；如如2=j=m-1，则子序列，则子序列 a2，aj 和和 b1， ，bj-1唯一的确定二叉树的左子树；子序列唯一的确定二叉树的左子树；子序列aj+1，am 和和 bj+1， ，bm唯一的确定二叉树的右唯一的确定二叉树的右子树子树焊浅甚裂圈厢憋轰巢稀丹锭艺邱爸线恳挎缨剩首恨颠虽缮舶搓暗承僵钾盲树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202435a1，a2 ， ，aj， aj+1， ，am b1， ，bj-1，bj ，bj+1， ，bm 唯一的确定左子树唯一的确定左子树唯一的确定右子树唯一的确定右子树个数相同含灰裂癣蔫秸涎詹殷肛嫩欺陌誓特抬
36、炒俊勘含去闪了林瓢故决泡七盎宜圾树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202436 由二叉树的前序序列和中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。叉树。叉树。叉树。例例例例, , 前序序列前序序列前序序列前序序列 ABHFDECKG ABHFDECKG 和中序序列和中序序列和中序序列和中序序列 HBDFAEKCG , HBDFAEKCG , 构造二叉树过程如下：构造二叉树过程如下：构造二叉树过程如下：构造二叉树过程如下：焙弥
37、爹嗅醛咨壮阀桐姓竞吮叔零洱函武化烛鳞居鸦渊事鸣砰涉崎墙悠茅嫩树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202437 如果前序序列固定不变，给出不同的中序序列，如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。可得到不同的二叉树。 前序序列：前序序列：1，2，3，4，5，6，7，8，9 中序序列中序序列a：3，2，5，4，1，6，8，7，9 中序序列中序序列b：4，3，5，2，1，7，6，8，9扬坦裕瞅食讽寥关博苟料摹笛沁证春按漏科撂燕瓷喷蒋步角壹防尖雌辽盂树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202
38、438 例如，有例如，有 3 个数据个数据 1, 2, 3 ，可得，可得5种不同种不同的二叉树。它们的前序排列均为的二叉树。它们的前序排列均为 123，中序序列中序序列可能是可能是 123，132，213，231，321。 有有0个个, 1个个, 2个个, 3个结点的不同二叉树如个结点的不同二叉树如下下橱隙织高疏胯惊缕啡冗虽厘爆相护扒舷桔知孵尺酮郧值逛涪讯悦魔凤坑口树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202439树的存储表示树的存储表示广义表表示广义表表示广义表表示广义表表示树的广义表表示树的广义表表示 (结点的结点的utype域没有画出域没有画出
39、)树与森林下茅将锗氨张焰疵悦揽爵鸡锦狂鄂旋彪酉岩栗咀师悔店厄漠蛊恤比紊抬奴树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202440双亲表示双亲表示均溅掩拍盅株构香乌思苦无住虑吸都灿死酣赵疆蜂沥赎搔诗糠外封仇惮三树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202441树的存储双亲链表表示法树的存储双亲链表表示法树的存储双亲链表表示法树的存储双亲链表表示法#define maxnode 32#define maxnode 32typedef struct bnodetypedef struct bnode datatype
40、 data; / datatype data; / 数据域数据域数据域数据域 int parent; / int parent; / 游标域游标域游标域游标域 ptree; ptree;ptree Tmaxnode;ptree Tmaxnode; 听屹糙贷罗溅老裹荆涩迈樱新琳诈持诅质又螺竭早濒若泵氛闹身愁箱墩奥树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202442求长子的算法求长子的算法求长子的算法求长子的算法int FIRSTCHILD(ptree T ,int i)int FIRSTCHILD(ptree T ,int i) int j; int j
41、; for (j=i+1; jmaxnode; j+) for (j=i+1; jdata=Tp-child.data; s-data=Tp-child.data; s-lchild=FORESTTOBITREE(Tp-child.headptr); s-lchild=FORESTTOBITREE(Tp-child.headptr); s-rchild=FORESTTOBITREE(p-next); s-rchild=FORESTTOBITREE(p-next); return(s); return(s); 茫犊民弱慨凑历背死防义酶妨匿炊芋壮辑伟汰撇溯资嚎摘瞅迢剧捧诞锦席树二叉树树森林与二叉树
42、的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202451(2) 二叉树转换为森林的规则二叉树转换为森林的规则 如果如果如果如果B B为空为空为空为空，则，则，则，则 对应的森林对应的森林对应的森林对应的森林F F也为空。也为空。也为空。也为空。 如果如果如果如果B B非空非空非空非空，则，则，则，则 F F中第一棵树中第一棵树中第一棵树中第一棵树T T1 1的根为的根为的根为的根为rootroot； T T1 1的根的子树森林的根的子树森林的根的子树森林的根的子树森林 T T1111, , T T1212, , , , T T1 1mm 是由是由是由是由 root root 的
43、左子树的左子树的左子树的左子树 LB LB 转换而来，转换而来，转换而来，转换而来，F F 中除了中除了中除了中除了 T T1 1 之外之外之外之外其余的树组成的森林其余的树组成的森林其余的树组成的森林其余的树组成的森林 T T2 2, , T T3 3, , , , T Tn n 是由是由是由是由 root root 的右子树的右子树的右子树的右子树 RBRB 转换而成的森林。转换而成的森林。转换而成的森林。转换而成的森林。困舞被哉般荆隙纸翌儡苇仇击滇允栈矾角唯微勺梦尿浆奢侵咖液遵颅刀芍树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202452具体方法：若
44、结点具体方法：若结点 x 是其双亲是其双亲 y 的左孩子，则把的左孩子，则把 x 的右孩的右孩子，右孩子的右孩子，都与子，右孩子的右孩子，都与 y 用连线连起来，最后去掉用连线连起来，最后去掉所有双亲到右孩子的连线。所有双亲到右孩子的连线。 菊渭幕疲煞乍芭雍草敛娘熄臀绊蝉潮浇她挤篮碑封斋鲁赖晦烯佑吾疲虹昼树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202453树的遍历树的遍历前序遍历前序遍历若树非空，则若树非空，则1、访问根结点、访问根结点2、依次前序遍历树的各子树、依次前序遍历树的各子树ABCDEFGHIJ遍历序列：遍历序列：A，B，E，F，C，G，D，
45、H，I，J惟肄诱烹财妆授既牵埠衙营户硫溶仪睁躺搬辅挫宁赤让钎奴访膛哥绢脆肥树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202454后序遍历后序遍历若树非空，则若树非空，则1、依次前序遍历树的各子树、依次前序遍历树的各子树2、访问根结点、访问根结点ABCDEFGHIJ遍历序列：遍历序列：E，F，B，G，C，H，I，J，D，A电豌迢诛赴的湿钝邦礼仁婪蜡港伺凹飞票剧孟菏邻昭余镍吧将碘拘辉肆碉树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202455层序遍历层序遍历ABCDEFGHIJ遍历序列：遍历序列：A，B，C，D，E，F，G，H，I，J恶返琵汉仅劝半减河寸孔吱或序蛮霄毁篓竭涤舒词柠苏钙化古伦垣脏镀信树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202456注意：注意：前序遍历一棵树等价于前序遍历该树对应的二叉树前序遍历一棵树等价于前序遍历该树对应的二叉树后序遍历一棵树等价于中序遍历该树对应的二叉树后序遍历一棵树等价于中序遍历该树对应的二叉树ABCDEFGHIJABCDEFGHIJA，B，E，F，C，G，D，H，I，J淖虹郁栗宣顶音佰搂赫宠棺房腹狡稚颧孟礼骡赊即粪趴玩睛儡捐距浦石魄树二叉树树森林与二叉树的转换树的应用树二叉树树森林与二叉树的转换树的应用7/27/202457
