树（三） 2012初赛知识点梳理.

Presentation on theme: "树（三） 2012初赛知识点梳理."— Presentation transcript:

1 树（三） 2012初赛知识点梳理

2 给出一棵二叉树的 中序遍历：DBGEACHFI 后序遍历：DGEBHIFCA 画出此二叉树。

3 给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。
【问题分析】 　　后序遍历中最后访问的是根结点，所以后序遍历DGEBHIFCA序列中A是根结点；根据中序遍历的算法，先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树，所以中序遍历DBGEACHFI序列中，根结点A的两侧分别是左子树和右子树：DBGE、CHFI。

4 由中根序列和后根序列来确定二叉树的结构，从而判断先根遍历序列及其它。
例1：(NOIP 2001提高组试题) 已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：C B G E A F H D I J与C G E B H F JI D A则该二叉树的先序遍历的顺序为 解析：已知中序序列为C B G E A F H D I (1) 后序序列为C G EBH F JI D A。(2) 由(2)知：根结点为A 由(1)知：A的左子树中序序列为C B G E (3) A的右子树中序序列为F H D I J(4) 由(2)知：A的左子树后序序列为C G E B(5) A的右子树后序序列为H F J I D(6) 由(5)(6)知：A的左子树根结点为B，A的右子树根结点为D 由(3)(4)知：B的左子树为C，右子树中序序列为G E D的左子树中序序列为F H，右子树中序序列为I J 由(5)(6)知：B的右子树后序序列为G E，即根结点为E D的左子树后序序列为H F，即根结点为F D的右子树后序序列为JI，即根结点为I 综上可推出二叉树的结构如图所示 故该二叉树的先序遍历序列为：A B C E G D F H I J

5 由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它
例2：(NOIP 2004提高组试题)二叉树T 已知其前序遍历序列为 中序遍历序列为 则其后序遍历序列为( )。 A． B． C． D． E． l

6 由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它
例2：(NOIP 2004提高组试题)二叉树T，已知其前序遍历序列为 ，中序遍历序列为 ，则其后序遍历序列为( )。 A． B． C． D． E． l 解析：已知前序遍历序列为 (1) 中序遍历序列为4 2 l (2) 由(1)知：根结点为1 由(2)知：1的左子树中序序列为4 2 (3) 右子树中序序列为 (4) 由(1)知1的左子树先序序列为2 4 (5) 1的右子树先序序列为 (6) 由(3)(5)知：1的左子树根结点为2，2的左子树为4 由(4)(6)知：1的右子树根结点为3 由(4)知：3的左子树中序序列为 (7) 3的右子树为6 由(6)(7)知：3的左子树根结点为5，且5的右子树为7 综上对应的一棵二叉树的结构如图所示： 故其后序遍历序列为： 从而答案选B

7 由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他
例3：(NOIP 2007提高组第14题)已知7个结点的二叉树的先根遍历是 f数字为结点的编号，以下同)，后根遍历是 ，则该二叉树的可能的中根遍历是( )。 A． B． C． D．

8 由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他
例3：(NOIP 2007提高组第14题)已知7个结点的二叉树的先根遍历是 f数字为结点的编号，以下同)，后根遍历是 ，则该二叉树的可能的中根遍历是( )。 A． B． C． D． 解析：先根遍历序列是 (1) 后根遍历序列是 (2) 由(1)和(2)知：根结点为l，1的左子树根结点是2，右子树根结点是3，结点4是结点2的左子树，可以判断结点5是结点2的右子树的根结点，但结点6可能是结点5的左子树，也可能是它的右子树，同样结点7可能是结点3的左子树，也可能是它的右子树。对应的二叉树的结构可能是如下四种： 图①的中序遍历序列是： 图②的中序遍历序列是： 图③的中序遍历序列是： 图④的中序遍历序列是： 故此题的答案应选A B D

9 通过二叉树的宽度优先遍历和树中结点的最大深度及结点之间的关系来判断树的结构，从而解决有关问题。
例5：(NOIP 2005提高组试题)二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3(根结点深度设为0)，可知E的父结点可能是 ( )。 A B． B C． C D． D E． F

10 通过二叉树的宽度优先遍历和树中结点的最大深度及结点之间的关系来判断树的结构，从而解决有关问题。
例5：(NOIP 2005提高组试题)二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3(根结点深度设为0)，可知E的父结点可能是 ( )。 A B． B C． C D． D E． F 解析：二叉树的宽度优先遍历就是按层遍历，从根结点自上而下，自左向右访问树中的每一个结点。由题目可知A是根结点，又知A是C的父结点，可以推知B是A的左子树的根结点，C是A的右子树的根结点。又知D是G的父结点，F是I的父结点，树中所有结点的最大深度为3，故E结点可能是B结点的右子树，也可能是G结点的左子树。二叉树的部分结构图为下图①②所示： 故E的父结点可能是B，也可能是C。

11 特殊二叉树 二叉排序树 又称二叉查找树，它可以是一棵空树或者具有如下特性的非空树：
特殊二叉树 二叉排序树 （1）二叉排序树定义：（假设从小到大排列） 又称二叉查找树，它可以是一棵空树或者具有如下特性的非空树： 若左子树不为空，则左子树上所有结点的值或关键字均小于根结点的值或关键字； 若右子树不为空，则右子树上所有结点的值或关键字均大于根结点的值或关键字； 左、右子树本身又各是一棵二叉树。

12 这种二叉排序树具有左小右大的特点。根据需要也可以构造左大右小的二叉排序树。
10 3 18 2 8 15 19 6 9 二叉排序树 特点： 对二叉排序树进行中序遍历，可得到一个由小到大的序例。 例如对图6.18的二叉排序树进行中根遍历: 则得到序列：2，3，6，8，9，10，15，18，19。

13

14 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。 给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： 　　(a)WPL=7*2+5*2+2*2+4*2=36 　　(b)WPL=7*3+5*3+2*1+4*2=46 　　(c)WPL=7*1+5*2+2*3+4*3=35 　　其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

15 给定权值 {7，5，2，4}，构造哈夫曼树 7 5 c d (b) a b c d (a) a c d b (d) b 7 c d (c)
6 7 5 c d (b) a b c d 7 5 2 4 (a) a 7 11 c d b 5 6 2 4 (d) 18 11 b 5 7 c d (c) 6

16 5,29,7,8,14,23,3,11

17 它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271

18 补充：哈夫曼树的应用 用于最佳判断过程 在考查课记分时往往把百分制转换成优（ x>=90 ）、良 (80<x<90) 、中 (70<=x80) 、及格 (60<=x<70) 、不及格 (x<60) 五个等级。若不考虑学生考试分数的分布概率，程序判定过程很容易写成图 6.23(a) 所示的方法。我们知道，一般来讲学生考分大多分布在 70 至 80 分之间，从图 6.23(a) 可看出这种情的 x 值要比较 2 至 3 次才能确定等级。而学生中考试不及格的人数很少， x 值比较一次即可定等级。能否使出现次数多的在 70 至 80 分之间的 x 值比较次数减少些，而使很少出现的低于 60 分的 x 值比较次数多一些，以便提高程序的运行效率呢？假设学生成绩对于不及格、及格、中等、良好和优秀的分布概率分别为 5 ％， 15 ％， 40 ％， 30 ％， 10 ％，以它们做为叶子的权值来构造哈夫曼树，如图 6.23(b) 所示。此时带权路径长最短，其值为 205 ％。它可以使大部分的分数值经过较少的比较次数得到相应的等级。但是，事务往往不是绝对的，此时每个判断柜内的条件较为复杂，比较两次，反而降低运行效率。所以我们采用折衷作法，调整后得图 6.23(c) 判定树。它更加切合实际。

19

20 (2) 用于通信编码 在通信及数据传输中多采用二进制编码。 例如:假设需传送的电文为: “A B A C C D A A” (1)令:A:00 B:01 C:10 D:11 则: 网络通信带宽越来越大,仍需进行数据压缩,即:传送电文时,总希望长度越来越短. (2)不等长的编码: 令:A:0 B: 则: C: 特点:接受方很难接受. D:01

21 (3)前缀编码: 长短不等的编码,但任一个字符的编码都不是另一个字符的编码的前缀. 如何得到使电文总长最短的二进制前缀编码呢? 当成叶子的权值构造哈夫曼树. 为什么?频率越高,编码越短,则总长越短. (1)构造哈夫曼树: (2)令: 所有的左分支为0 所有的右分支为1

22

23

24