《树二树树森林与二叉树的转换树的应用》由会员分享，可在线阅读，更多相关《树二树树森林与二叉树的转换树的应用（57页珍藏版）》请在金锄头文库上搜索。
1、树树二叉树二叉树树、森林与二叉树的转换树、森林与二叉树的转换树的应用树的应用第五章第五章 树和二叉树树和二叉树8/24/20241树和森林的概念树和森林的概念树的定义树的定义树的定义树的定义 树是由树是由树是由树是由n n ( (n n 0) 0)个结点组成的有限集合。如果个结点组成的有限集合。如果个结点组成的有限集合。如果个结点组成的有限集合。如果n n = 0= 0，称为空树；如果称为空树；如果称为空树；如果称为空树；如果n n 0 0，则则则则 有一个特定的称之为有一个特定的称之为有一个特定的称之为有一个特定的称之为根根根根(root)(root)的结点，它只有的结点，它只有的结点，它只
2、有的结点，它只有直接后继，但没有直接前驱；直接后继，但没有直接前驱；直接后继，但没有直接前驱；直接后继，但没有直接前驱； 除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为除根以外的其它结点划分为mm ( (mm 0) 0)个互不相个互不相个互不相个互不相交的有限集合交的有限集合交的有限集合交的有限集合T T0 0, , T T1 1, , , , T Tmm-1-1，每个集合又是一棵树，每个集合又是一棵树，每个集合又是一棵树，每个集合又是一棵树，并且称之为根的并且称之为根的并且称之为根的并且称之为根的子树子树子树子树( (subTreesubTree) )。每棵子树的根
3、结点每棵子树的根结点每棵子树的根结点每棵子树的根结点有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有有且仅有一个直接前驱，但可以有0 0个或多个直接后个或多个直接后个或多个直接后个或多个直接后继。继。继。继。8/24/20242树的表示树的表示树的表示树的表示 树型表示树型表示树型表示树型表示bacghdefij8/24/20243凹入表表示凹入表表示凹入表表示凹入表表示abdeijfcgh8/24/20244嵌套集合表示嵌套集合表示嵌套集合表示嵌套集合表示嵌套括号表示嵌套括号表示嵌套括号表示嵌套括号表示ijdfghabcea ( b ( d, e (
4、 i, j ), c ( g, h ) ) )8/24/20245 结点结点结点结点(node)(node)(node)(node) 结点的度结点的度结点的度结点的度(degree) (degree) (degree) (degree) 结点的子树个数结点的子树个数结点的子树个数结点的子树个数 分支分支分支分支(branch)(branch)(branch)(branch)结点结点结点结点 度不为度不为度不为度不为0 0 0 0的结点的结点的结点的结点 叶叶叶叶(leaf)(leaf)(leaf)(leaf)结点结点结点结点 度为度为度为度为0 0 0 0的结点的结点的结点的结点 子女子女子女
5、子女(child)(child)(child)(child)结点结点结点结点 某结点子树的根结点某结点子树的根结点某结点子树的根结点某结点子树的根结点 双亲双亲双亲双亲(parent)(parent)(parent)(parent)结点结点结点结点 某个结点是其子树之根的某个结点是其子树之根的某个结点是其子树之根的某个结点是其子树之根的 双亲双亲双亲双亲 8/24/20246 兄弟兄弟兄弟兄弟(sibling)(sibling)(sibling)(sibling)结点结点结点结点 具有同一双亲的所有结点具有同一双亲的所有结点具有同一双亲的所有结点具有同一双亲的所有结点 祖先祖先祖先祖先(anc
6、estor)(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)(descendant)(descendant)(descendant)结点结点结点结点 若树中结点若树中结点若树中结点若树中结点k k k k到到到到k k k ks s s s存在一条路径，存在一条路径，存在一条路径，存在一条
7、路径， 则称则称则称则称k k k ks s s s是是是是k k k k的子孙的子孙的子孙的子孙 结点所处层次结点所处层次结点所处层次结点所处层次(level) (level) (level) (level) 根结点的层数为根结点的层数为根结点的层数为根结点的层数为1 1 1 1，其余结点的层，其余结点的层，其余结点的层，其余结点的层 数为双亲结点的层数加数为双亲结点的层数加数为双亲结点的层数加数为双亲结点的层数加1 1 1 1 树的高度树的高度树的高度树的高度(depth) (depth) (depth) (depth) 树中结点的最大层数树中结点的最大层数树中结点的最大层数树中结点的最大
8、层数 树的度树的度树的度树的度(degree)(degree)(degree)(degree)n n 有序树有序树有序树有序树 子树的次序不能互换子树的次序不能互换子树的次序不能互换子树的次序不能互换n n 无序树无序树无序树无序树 子树的次序可以互换子树的次序可以互换子树的次序可以互换子树的次序可以互换n n 森林森林森林森林 互不相交的树的集合互不相交的树的集合互不相交的树的集合互不相交的树的集合8/24/20247树的基本操作树的基本操作1 1、初始化、初始化、初始化、初始化2 2、求指定结点所在树的根结点、求指定结点所在树的根结点、求指定结点所在树的根结点、求指定结点所在树的根结点3
9、3、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点、求指定结点的双亲结点4 4、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点、求指定结点的某一孩子结点5 5、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点、求指定结点的最右边兄弟结点6 6、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它、将一棵树插入到另一树的指定结点下作为它 的子树的子树的子树的子树7 7、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结点的某一子树、删除指定结
10、点的某一子树8 8、树的遍历、树的遍历、树的遍历、树的遍历8/24/20248二叉树二叉树 (Binary Tree)二叉树的定义二叉树的定义二叉树的五种不同形态二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该集合一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。为左子树和右子树的、互不相交的二叉树组成。8/24/20249性质性质性质性质1 1 若二叉树的层次从若二叉树的层次从若二叉树的层次从若二叉树的层次从1 1开始开始开始开始, , 则在二叉树的则在二叉树的则在二叉树
11、的则在二叉树的 第第第第 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层结点层结点层结点层结点的两倍，即总的结点个数至多为的
12、两倍，即总的结点个数至多为的两倍，即总的结点个数至多为的两倍，即总的结点个数至多为2222k-1 k-1 = = 2 2k k故命题成立故命题成立故命题成立故命题成立8/24/202410性质性质性质性质2 2 高度为高度为高度为高度为k k的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有 2 2k k-1-1个结点。个结点。个结点。个结点。 ( (k k 1) 1)证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质的结点数最多，利用性质的结点数最
13、多，利用性质的结点数最多，利用性质1 1可得二叉树的结点数可得二叉树的结点数可得二叉树的结点数可得二叉树的结点数至多为：至多为：至多为：至多为：2 20 0 + + 2 21 1 + + 2 22 2 + + 2 23 3 + + + + 2 2k-1 k-1 = = 2 2k k 1 1 8/24/202411性质性质性质性质3 3 对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树, , 如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为如果其叶结点个数为 n n0 0, , 度为度为度为度为2 2的非叶结点个数为的非叶结点个数为的非叶结点个数为的非叶结点个数为 n n2
14、 2, , 则有则有则有则有 n n0 0n n2 21 1证明：证明：证明：证明：1 1、结点总数为度为、结点总数为度为、结点总数为度为、结点总数为度为0 0的结点加上度为的结点加上度为的结点加上度为的结点加上度为1 1的结点再加上度的结点再加上度的结点再加上度的结点再加上度 为为为为2 2的结点：的结点：的结点：的结点： n = nn = n0 0 + n + n1 1 + n + n2 22 2、另一方面，二叉树中一度结点有一个孩子，二另一方面，二叉树中一度结点有一个孩子，二另一方面，二叉树中一度结点有一个孩子，二另一方面，二叉树中一度结点有一个孩子，二 度结度结度结度结 点有二个孩子，
15、根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此，点有二个孩子，根结点不是任何结点的孩子，因此， 结点总数为：结点总数为：结点总数为：结点总数为： n = nn = n1 1 + 2n + 2n2 2 + 1+ 13 3、两式相减，得到：两式相减，得到：两式相减，得到：两式相减，得到： n n0 0 = n = n2 2 + 1 + 1 8/24/202412定义定义1 满二叉树满二叉树(Full Binary Tree) 一棵深度为一棵深度为k 且有且有2k-1个结点的二叉树。个结点的二叉树。定义定义2 完全二叉树完全
16、二叉树(Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有则共有h+1层。层。除第除第h层外，其它各层层外，其它各层(0 h-1)的结点数都达的结点数都达到最大个数，第到最大个数，第h层从右向左连续缺若干结层从右向左连续缺若干结点，这就是完全二叉树。点，这就是完全二叉树。8/24/202413性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度 为为 log2n + +1证明：设完全二叉树的高度为证明：设完全二叉树的高度为h h，则有则有 2 2h-1h-1 - 1 - 1 n n 2 2h h - 1 - 1 2 2h-1h-1 =
17、= 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-datachch; ; s- s-lchildlchildNULL;NULL; s- s-rchildrchildNULL;NULL; 8/24/202423 rear+; Qrearrear+; Qrears;s; if (rear=1) r
18、oot if (rear=1) roots;s; else else if (s&Qfront) if (s&Qfront) if (rear%2=0) Qfront- if (rear%2=0) Qfront-lchildlchilds;s; else Qfront- else Qfront-rchildrchilds;s; if (rear%2=1) front+; if (rear%2=1) front+; chch= =getchargetchar();(); return root; return root;8/24/202424中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是
19、：中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是： 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L)(L)； 访问根结点访问根结点访问根结点访问根结点 (V)(V)； 中序遍历右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R)(R)。遍历结果遍历结果遍历结果遍历结果 a a + + b b * * c c - - - - d d - - - - e e / / f f中序遍历表达式语法树表达式语法树二叉树的遍历8/24/202425中序遍历算法中序遍
20、历算法INORDER(bitreeINORDER(bitree * *cntcnt) ) if ( if (cntcnt) ) INORDER(t- INORDER(t-lchlch);); printf(printf(“t%cnt%cn”,t,t-data);-data); INORDER(t- INORDER(t-rchrch);); 8/24/202426中序遍历二叉树的递归过程图解中序遍历二叉树的递归过程图解8/24/202427前序遍历前序遍历二叉树算法的框架是前序遍历二叉树算法的框架是前序遍历二叉树算法的框架是前序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操
21、作；若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 访问根结点访问根结点访问根结点访问根结点 (V)(V)； 前序遍历左子树前序遍历左子树前序遍历左子树前序遍历左子树 (L)(L)； 前序遍历右子树前序遍历右子树前序遍历右子树前序遍历右子树 (R)(R)。遍历结果遍历结果遍历结果遍历结果- - - - + + a a * * b b - - - - c dc d / / e fe f8/24/202428后序遍历后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为
22、空，则空操作；若二叉树为空，则空操作； 否则否则否则否则 后序遍历左子树后序遍历左子树后序遍历左子树后序遍历左子树 (L)(L)； 后序遍历右子树后序遍历右子树后序遍历右子树后序遍历右子树 (R)(R)； 访问根结点访问根结点访问根结点访问根结点 (V)(V)。遍历结果遍历结果遍历结果遍历结果a b c da b c d - - - - * + * + e fe f / / - - - -8/24/202429层序遍历层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是层序遍历二叉树算法的框架是 若二叉树为空，则空操作；若二叉树为空，则空操作；若二叉树为空，则空操作；
23、若二叉树为空，则空操作； 否则，如队列不空，循环：否则，如队列不空，循环：否则，如队列不空，循环：否则，如队列不空，循环： 根结点入队，并作为当前结点；根结点入队，并作为当前结点；根结点入队，并作为当前结点；根结点入队，并作为当前结点；将当前结点的左右孩子入队；将当前结点的左右孩子入队；将当前结点的左右孩子入队；将当前结点的左右孩子入队； 做出队操作，队首元素作为当做出队操作，队首元素作为当做出队操作，队首元素作为当做出队操作，队首元素作为当 前结点前结点前结点前结点 最后，出队序列就是层序遍历最后，出队序列就是层序遍历最后，出队序列就是层序遍历最后，出队序列就是层序遍历 序列序列序列序列遍历
24、结果遍历结果遍历结果遍历结果- - - - + / + / a a * * e fe f b b - - - - c dc d 8/24/202430例：在二叉树中查找具有给定值的结点例：在二叉树中查找具有给定值的结点bitreebitree findnode(bitreefindnode(bitree *t, *t, datatypedatatype x) x) if ( t = NULL) return(NULL); if ( t = NULL) return(NULL); else if ( t-data = x) return(t); else if ( t-data = x) ret
25、urn(t); else return( else return( findnode(tfindnode(t-lchildlchild)|)| findnode(tfindnode(t-rchildrchild) ) ) 8/24/202431例：给定一棵二叉树，输出其嵌套括号表示例：给定一棵二叉树，输出其嵌套括号表示void void print(bitreeprint(bitree *t) *t) if (t) if (t) printf(printf(“%d%d”, t-data);, t-data); if (t- if (t-lchildlchild |t- |t-rchildrch
26、ild) ) printfprintf( (“( (”);); printf(lchildprintf(lchild);); if (t- if (t-rchildrchild) ) printfprintf( (“, ,”);); print(rchildprint(rchild);); printfprintf( (“) )”); ); 8/24/202432例：求二叉树的深度例：求二叉树的深度void void depth(bitreedepth(bitree *t) *t) intint dep1, dep2; dep1, dep2; if (t = = NULL) return(0)
27、; if (t = = NULL) return(0); else else dep1 = depth(t- dep1 = depth(t-lchildlchild);); dep2 = depth(t- dep2 = depth(t-rchildrchild);); if (dep1 dep2) return(dep1 + 1); if (dep1 dep2) return(dep1 + 1); else return(dep2 + 1); else return(dep2 + 1); 8/24/202433例：证明：一棵二叉树的前序序列和中序序列可例：证明：一棵二叉树的前序序列和中序序列可
28、以唯一的确定这棵二叉树。以唯一的确定这棵二叉树。用归纳法证明：用归纳法证明：1、当、当 n = 1时，结论显然成立；时，结论显然成立；2、假定当、假定当 n = k 时，结论成立；时，结论成立；3、当、当 n = k + 1 时，假定前序序列为和中序序列时，假定前序序列为和中序序列分分 别为：别为： a1，am 和和 b1， ，bm 8/24/202434 如中序序列中与前序序列如中序序列中与前序序列a1相同的元素为相同的元素为bj。j = 1时，二叉树无左子树，由时，二叉树无左子树，由 a2，am 和和 b2， ，bm 可以唯一的确定二叉树的右子树；可以唯一的确定二叉树的右子树；j = m时
29、，二叉树无右子树，由时，二叉树无右子树，由 a2，am 和和 b1， ，bm-1 可以唯一的确定二叉树的左子树；可以唯一的确定二叉树的左子树；如如2=j=m-1，则子序列则子序列 a2，aj 和和 b1， ，bj-1唯一的确定二叉树的左子树；子序列唯一的确定二叉树的左子树；子序列aj+1，am 和和 bj+1， ，bm唯一的确定二叉树的右唯一的确定二叉树的右子树子树8/24/202435a1，a2 ， ，aj， aj+1， ，am b1， ，bj-1，bj ，bj+1， ，bm 唯一的确定左子树唯一的确定左子树唯一的确定右子树唯一的确定右子树个数相同8/24/202436 由二叉树的前序序列和
30、中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。叉树。叉树。叉树。例例例例, , 前序序列前序序列前序序列前序序列 ABHFDECKG ABHFDECKG 和中序序列和中序序列和中序序列和中序序列 HBDFAEKCG , HBDFAEKCG , 构造二叉树过程如下：构造二叉树过程如下：构造二叉树过程如下：构造二叉树过程如下：8/24/202437 如果前序序列固定不变，给出不同的中序序列，如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。可得到不同的二叉树。 前
31、序序列：前序序列：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，98/24/202438 例如，有例如，有 3 个数据个数据 1, 2, 3 ，可得，可得5种不同种不同的二叉树。它们的前序排列均为的二叉树。它们的前序排列均为 123，中序序列中序序列可能是可能是 123，132，213，231，321。 有有0个个, 1个个, 2个个, 3个结点的不同二叉树如个结点的不同二叉树如下下8/24/202439树的存储表示树的存储表示广义表表示广义表表示广义表表示广义表表示树的广义表表示树的广义表表示
32、(结点的结点的utype域没有画出域没有画出)树与森林8/24/202440双亲表示双亲表示8/24/202441树的存储双亲链表表示法树的存储双亲链表表示法树的存储双亲链表表示法树的存储双亲链表表示法#define #define maxnodemaxnode 32 32typedeftypedef structstruct bnodebnode datatypedatatype data; / data; / 数据域数据域数据域数据域 intint parent; / parent; / 游标域游标域游标域游标域 ptreeptree; ;ptreeptree TmaxnodeTmaxno
33、de; ; 8/24/202442求长子的算法求长子的算法求长子的算法求长子的算法intint FIRSTCHILD(ptreeFIRSTCHILD(ptree T , T ,intint i) i) intint j; j; for (j=i+1; j for (j=i+1; jdata=Tp-child.data; s-data=Tp-child.data; s- s-lchildlchild=FORESTTOBITREE(Tp-=FORESTTOBITREE(Tp-child.headptrchild.headptr);); s- s-rchildrchild=FORESTTOBITRE
34、E(p-next);=FORESTTOBITREE(p-next); return(s); return(s); 8/24/202451(2) 二叉树转换为森林的规则二叉树转换为森林的规则 如果如果如果如果B B为空为空为空为空，则，则，则，则 对应的森林对应的森林对应的森林对应的森林F F也为空。也为空。也为空。也为空。 如果如果如果如果B B非空非空非空非空，则，则，则，则 F F中第一棵树中第一棵树中第一棵树中第一棵树T T1 1的根为的根为的根为的根为rootroot； T T1 1的根的子树森林的根的子树森林的根的子树森林的根的子树森林 T T1111, , T T1212, , ,
35、 , T T1 1mm 是由是由是由是由 root root 的左子树的左子树的左子树的左子树 LB LB 转换而来，转换而来，转换而来，转换而来，F F 中除了中除了中除了中除了 T T1 1 之外之外之外之外其余的树组成的森林其余的树组成的森林其余的树组成的森林其余的树组成的森林 T T2 2, , T T3 3, , , , T Tn n 是由是由是由是由 root root 的右子树的右子树的右子树的右子树 RBRB 转换而成的森林。转换而成的森林。转换而成的森林。转换而成的森林。8/24/202452具体方法：若结点具体方法：若结点 x 是其是其双亲双亲 y 的的左孩子，则把左孩子，
36、则把 x 的的右孩右孩子，右孩子的右孩子，都与子，右孩子的右孩子，都与 y 用连线连起来，最后去掉用连线连起来，最后去掉所有双亲到右孩子的连线。所有双亲到右孩子的连线。 8/24/202453树的遍历树的遍历前序遍历前序遍历若树非空，则若树非空，则1、访问根结点、访问根结点2、依次前序遍历树的各子树、依次前序遍历树的各子树ABCDEFGHIJ遍历序列：遍历序列：A，B，E，F，C，G，D，H，I，J8/24/202454后序遍历后序遍历若树非空，则若树非空，则1、依次前序遍历树的各子树、依次前序遍历树的各子树2、访问根结点、访问根结点ABCDEFGHIJ遍历序列：遍历序列：E，F，B，G，C，H，I，J，D，A8/24/202455层序遍历层序遍历ABCDEFGHIJ遍历序列：遍历序列：A，B，C，D，E，F，G，H，I，J8/24/202456注意：注意：前序遍历一棵树等价于前序遍历该树对应的二叉树前序遍历一棵树等价于前序遍历该树对应的二叉树后序遍历一棵树等价于中序遍历该树对应的二叉树后序遍历一棵树等价于中序遍历该树对应的二叉树ABCDEFGHIJABCDEFGHIJA，B，E，F，C，G，D，H，I，J8/24/202457
