数据结构 课件 树和森林.ppt

1、树与森林,树与二叉树转换 森林的遍历 二叉树的计数 赫夫曼二叉树,树与二叉树转换,将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺

2、时针旋转，构成二叉树型结构,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,树的先序遍历 树的后序遍历 森林的先序遍历 森林的中序遍历,三、树和森林的遍历,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,遍历序列：,f,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,遍历序列：,访问树的根结点； 从左至右依次先序遍历根

3、的每棵子树。,1、树的先序遍历,a,b,e,f,g,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,c,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,c,d,h,i,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,c,d,h,i,j,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,c,d,h,i,j,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树

4、的先序遍历,a,b,e,f,g,c,d,h,i,j,遍历序列：,访问树的根结点； 从左至右依次先序遍历根的每棵子树。,1、树的先序遍历,a,b,e,f,g,c,d,h,i,j,遍历序列：,问：树的先序遍历序列与对应二叉树的哪种遍历序列相同？,1、树的先序遍历,答：树的先序遍历序列与对应二叉树的先序遍历序列相同。,树的先根次序遍历的递归算法,template void Tree: PreOrder ( TreeNode * current) /以当前指针current为根, 先根次序遍历 if (!current.IsEmpty () /树非空 visit (current);/访问根结点 Tr

5、eeNode *p = current; /暂存当前指针 current = current-firstChild; /第一棵子树 while (current != NULL) PreOrder (current);/递归先根遍历子树 current = current-nextSibling;, current = p;/恢复当前指针 ;,思考:如何实现先序遍历某个文件目录?,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,遍历序列：,从左至右，依次后序遍历根的每棵子

6、树； 访问树的根结点。,2、树的后序遍历,e,f,g,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,i,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,i,j,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,i,j,

7、h,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,i,j,h,d,遍历序列：,从左至右，依次后序遍历根的每棵子树； 访问树的根结点。,2、树的后序遍历,e,f,g,b,c,i,j,h,d,a,遍历序列：,问：树的后序遍历序列与对应二叉树的哪种遍历序列相同？,2、树的后序遍历,答：树的后序遍历序列与对应二叉树的中序遍历序列相同。,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,遍历序列：,a,若森林非空，则： 访问森林中第一棵树的根结

8、点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,遍历序列：

9、,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b

10、,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中

11、根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,g,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a

12、,b,d,e,f,c,g,h,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,g,h,i,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,g,h,i,j,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中

13、根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,g,h,i,j,k,遍历序列：,若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。,3、森林的先序遍历,b,d,a,h,e,i,j,f,c,k,g,a,b,d,e,f,c,g,h,i,j,k,遍历序列：,问：森林的先序序列与对应二叉树的哪种遍历序列相同？,答：森林的先序序列与对应二叉树的先序遍历序列相同。,3、森林的先序遍历,二叉树的计数,二叉树遍历的结果是将一个

14、非线性结构中的数据通过访问排列到一个线性序列中。 前序序列：a b d c e 特点是第一个访问的a一定是树根，只要左子树非空，后面紧跟的b 一定是根的左子女， 中序序列：b d a e c 特点是树 根 a 把整个中序分成两部分， a 左侧子序列是根的左子树上 的结点数据，右侧子序列是根 的右子树上的结点数据。,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 A B H F D E C K G 和中序序列 H B D F A E K C G , 构造二叉树过程如下：,前序序列 A B H F D E C K G ,如果前序序列固定不变，给出不同的中序序列，可得到不同的二

15、叉树。 固定前序排列，选择所有可能的中序排列，可能构造多少种不同的二叉树？,例如, 有 3 个数据 1, 2, 3 ，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321，231，213，132，123。 前序序列为 123，中序序列为 312 的二叉树不存在。,有0个, 1个, 2个, 3个结点的不同二叉树如下,计算具有n个结点的不同二叉树的棵数,Catalan函数,bi,bn-i-1,1,相同的问题,不同二叉树数目 可能的出栈序列(元素1第i个出栈) 矩阵相乘的结合(课本227页),赫夫曼二叉树,赫夫曼二叉树 又称最优二叉树，是一类带权路径长度最短的二叉树。,1、基

16、本术语,二叉树的带权路径长度 二叉树中所有叶子结点的带权路径长度之和。,结点的带权路径长度 根到结点的路径长度结点的权。,根到结点的路径长度 从根到结点的路径上的分支数。,【例】设结点a、b、c、d的权值分别为1、3、5、7，,1、基本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度,1、基本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度3*1+3*3+2*5+1*729,1、基本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度3*1+3*3+2*5+1*729 二叉树的带权路径长度,1、基

17、本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度3*1+3*3+2*5+1*729 二叉树的带权路径长度2*1+2*3+2*5+2*732,1、基本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度3*1+3*3+2*5+1*729 二叉树的带权路径长度2*1+2*3+2*5+2*732 二叉树的带权路径长度,1、基本术语,【例】设结点a、b、c、d的权值分别为1、3、5、7， 二叉树的带权路径长度3*1+3*3+2*5+1*729 二叉树的带权路径长度2*1+2*3+2*5+2*732 二叉树的带权路径长度2*1+3*3+3

18、*5+1*733,1、基本术语,【赫夫曼算法】 根据给定的n个权值w1,w2,wn构成n棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树只含一个带权的根结 点，其左右子树均空；,2、构造赫夫曼二叉树,在F中选取两棵根结点的权值最小的二叉树为左右子树， 构造一棵新的二叉树，且置新的二叉树的根结点的权值 为其左、右子树上根结点的权值之和；,2、构造赫夫曼二叉树,d,a,c,b,7,1,5,3,在F中删除这两棵二叉树，同时将新得到的二叉树加入F ；,2、构造赫夫曼二叉树,d,a,c,b,7,1,5,3,在F中删除这两棵二叉树，同时将新得到的二叉树加入F ；,2、构造赫夫曼二叉树,d,c,7,5,

19、在F中删除这两棵二叉树，同时将新得到的二叉树加入F ；,2、构造赫夫曼二叉树,d,c,7,5,重复和，直到F只含一棵二叉树，此即最优二叉树。,2、构造赫夫曼二叉树,d,c,7,5,重复和，直到F只含一棵二叉树，此即最优二叉树。,2、构造赫夫曼二叉树,d,7,重复和，直到F只含一棵二叉树，此即最优二叉树。,2、构造赫夫曼二叉树,d,7,重复和，直到F只含一棵二叉树，此即最优二叉树。,2、构造赫夫曼二叉树,重复和，直到F只含一棵二叉树，此即最优二叉树。,2、构造赫夫曼二叉树,【问题】 设某系统在通信联络中只可能出现八种字符，其概率分 别为0.05、0.29、0.07、0.08、0.14、0.23、

20、0.03、0.11，要求 设计这些字符的二进制编码，以使通信中总码长尽可能短。,3、赫夫曼编码,【分析】 设八个字符分别为A(0.05)、B(0.29)、C(0.07)、D(0.08)、 E(0.14)、F(0.23)、G(0.03)、H(0.11)。 若用等长编码，则每个字符码长3位，若传递10000个字 符，则总码长为30000位。,3、赫夫曼编码,【分析】 若用不等长编码，则应使常用字符码长较短，非常用字 符码长略长，从而缩短总码长。但应注意二义性问题。,3、赫夫曼编码,例： 若令B(0.29)=0、F(0.23)=1、E(0.14)=00、H(0.11)=01、 D(0.08)=10、

21、C(0.07)=11、A(0.05)=000、G(0.03)=001，则传 递00110101，如何解释？(二义性的原因是: 其中一个码是另一个码的前缀),【赫夫曼编码方案】 以字符出现频率为权值，构造赫夫曼二叉树； 约定以左分支表示，右分支表示，把从根到叶子的路 径上所有分支构成的串作为叶子的二进制编码，即为 赫夫曼编码。,3、赫夫曼编码,例：,3、赫夫曼编码,例：,3、赫夫曼编码,d,0.08,c,0.07,b,0.29,h,0.11,e,0.14,f,0.23,例：,3、赫夫曼编码,d,0.08,c,0.07,b,0.29,h,0.11,e,0.14,f,0.23,例：,3、赫夫曼编码,b,0.29,h,0.11,e,0.14,f,0.23,g,a,0.08,例：,3