《树与二叉树典型例题讲解》由会员分享，可在线阅读，更多相关《树与二叉树典型例题讲解（35页珍藏版）》请在金锄头文库上搜索。
1、例题6.1 已知一棵度为m的树有n1个度为1的结点，n2个度为2的结点 ，nm个为m结点，问该树中有多少个叶子结点？ 解：设n为总结点个数，n0为叶子结点(即度为0的结点个数)，则有:n=n0+n1+n2+nm (1) 又有（分支总数）：n-1=n1*1+n2*2+n3*3+nm*m (2) （因为一个结点对应一个分支） 式(2)-(1)得: 1=n0-n2-2n3-(m-1)nm 则有:n0=1+n2+2n3+(m-1)nm练习 设树T的度为4，其中度为1，2，3和4的结 点个数分别为4，2，1，1 则T中的叶子数 为证明：二叉树度为0的结点总比度为2的结点多1个 因为二叉树所有结点滴个数都
2、不大于2，所以结点总数 n=n0+n1+n2 (1) 又因为度为1和度为2的结点分别有1个子树和2个子树，所以， 二叉树中子树结点就有n(子）=n1+2n2 二叉树中只有根节点不是子树结点，所以二叉树结点总数n=n(子 ）+1 即 n=n1+2n2+1 (2) 结合（1）式和（2）式就得n0=n2+1练习1、具有10个叶结点的二叉树中有（ ）个度为2的结点 A8 B9 C10 Dll 2、一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） Alogn+1 Blogn+1 Clogn Dlogn-1 3、一棵树高为K的完全二叉树至少有（ ）个结点。 A2k 1 B. 2k-1 1 C. 2k
3、-1 D. 2k例题6.2 写出如图6.2所示的二叉树的前(先)序中序和后序遍历序列. 解： 前序为“根左右”，从左到右收集的前序序列为：fdbacegihj； 中序为“左根右”，从左到右收集的中序序列为：abcdefghij； 后序为“左右根”，从左到右收集的后序序列为：acbedhjigf。fdgibehjac练习 一棵二叉树如图所示：写出对此树的先根 、中跟、后跟序列。 先根序列:ABDEFC 中根序列:DEFBAC 后根序列:FEDBCA已知先序和中序求后序 先序：ABCDEFGH 中序：BDCEAFHG 后序：已知中序和后序求先序 中序：BDCEAFHG 后序：DECBHGFA 求先
4、序：问题 已知先序和后序能求中序么?例题6.3 若一棵二叉树，左右子树均有三个结点，其左子树的前（先） 序序列与中序序列相同，右子树的中序序列与后序序列相同，试构 造该树。 【解】据题意，左子树的前序序列与中序序列相同，即有：前序： 根 左 右中序： 左 根 右也即，以左子树为根的树无左孩子。此处，右子树的中序序列与后序 序列相同，即有：中序： 左 根 右后序： 左 右 根也即，以右子树为根的树无右孩子。由此构造该树如下图所示。例题4 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二 叉树的形状。 解：先序遍历为“根左右”，后序遍历为“左右根”。 根结点在两个序列中的位置分别在最前和最
5、后，正好相反；因此，若要 两个序列正好相反，则左右子树必有一个不存在。其先序序列和后序序 列正好相反的二叉树必为单支树。即这棵二叉树的形状如下图所示 。 例题6.5 已知一棵完全二叉树共有892个结点，试求： 树的高度； 叶结点数； 单支(度为1)结点数； 最后一个非终端结点的序号。解：(1) 根据性质2，已知深度为k的二叉树至多有2k-1个结点(k1)，由于：29-1 892 210-1，所以树的高度为10。(2) 对完全二叉树来说，度为1的结点只能是0或1。由n=n0+n1+n2和n0=n2+1（性质3）得：设n1=0，则有892=n0+0+n2=n2+1+n2=2n2+1，因得到的n2=
6、891/2不为整数而出错；n1=1，则有892=n0+1+n2=n2+1+1 +n2=2n2+2，得n2=445，代入n0=n2+1得n0=446；故叶结点数为446。(3) 由解过程可知n1=1 ，单支结点数为1 。(4) 对有n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点n/2为最后一个非终端结点，则序号为892/2=446。此外，由可知：n2=445，n1=1；则最后一个非终端结点的序号为 445+1=446。 对于还可以采用如下：因89229-1，则前9层的结点数为29-1=511个 ；而第10层的结点为892-511=381个，且381个结点对应第9层的父结点
7、为381/2=191，而第9层的其余结点也是叶结点，即29-1=256，256- 191=65，故第9层共有65个叶结点，则第10层叶结点+第9层叶结点 =381+65=446。例题6.6 对如下图所示的二叉树: 写出对它们进行先序 中序和后序遍历时得到的结点序列; 画出它们的先序线索二叉树和后序线索二叉树。【解】 对图进行先序中序和后序遍历时得到的 结点序列分别如下: 先序遍历的结点序列为：ABDFGHIEC 中序遍历的结点序列为：FDHGIBEAC 后序遍历的结点序列为：FHIGDEBCAABCGDEHIF二叉树的先序线索二叉树如下左图所示，后序线索二叉树如下右图所示。ABCGDEHIFN
8、IL先序线索二叉树ABCGDEHIF后序线索二叉树NIL例题6.7 如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和 BDCAIFJGHE，请画出该森林。 【解】由于森林的前序序列与其对应的二叉树前序序列相同，而森林的 后序序列与其对应的二叉树中序序列相同。因此，根据二叉树前序序 列ABCDEFIGJH和中序序列BDCAIFJGHE可画出二叉树如下图所示。ABEDCGJIFH而由二叉树转化为森林的步骤得到对应的森林。ABDCEGJIFH例题6.8 证明n0个叶子结点的哈夫曼树共有2n0-1个结点。证明：设度为1和2的结点个数分别为n1和 n2，二叉树结点总数为n，则 有：n=n0+
9、n1+n2根据二叉树的性质知：n0=n2+1此外，由哈夫曼树的构造原理可知：哈夫曼树不存在度为1的结点，即 n1=0；所以由可得：n=n0+0+n2=n0+n0-1=2n0-1abcdefhgi601234578bdefghicdatafc1 23 48 675aCTree.r=0 CTree.n=9例6.9 用孩子链表结构表示西图所示的树612345789acdefghibdatafc2 34 59 7 86012235551parent abcdefhgiPCTree.r=1 PCTree.n=9例6.10 用带双亲的孩子链表表示下图所示的树例6.11 用孩子兄弟表示法表示下图所示的树(重
10、点掌握)abcdefhgibda c e f ghi与树对应的二叉树表示其根结 点无右子树。（1）树与二叉树转换ACBED树ABCDE二叉树A BC D E A B C D E A BC D E 对应存储存储解释解释例6.12 森林、树与二叉树转换（以二叉链表为纽带）森林转换成二叉树 将各棵树分别转换成二叉树（根结点均无右孩子）； 将各二叉树的根结点依次用分支线连起来； 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构 成二叉树型结构。 森林转化成二叉树的过程:ABCDEFGHIJ森林ABCDEFGHIJ对应二叉树ABCDEFGHIJABCDEFGHIJ连接跟结点旋转成二叉树例6
11、.13 二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子 间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ例6.14 Huffman编码设计实例已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05， 0.29，0.07，0.08，0.14， 0.23，0.03，0.11，试设计Huffman编码 。 解一：先构造Huffman树，再进行编码。Huffman编码实现过程：以报文所用的不同字符为叶结点，以字符 出现频率为权重构造Huffman树；然后将树中
12、结点指向其左孩子的 分支标“0”，指向其右孩子的分支标“1”；每个字符的编码即为 从根到每个叶子（字符）的路径上得到的0、1序列。这种对字符的 编码就是Huffman编码。11358192342291487152958100 01000011100111HC 1 0110 2 10 3 11104 1111 5 110 6 00 7 0111 8 011 Huffman编码Huffman树解二：利用Huffman编码算法实现。根据题意，取8个字符的权分别为 （5，29，7，8，14，23，3，11），n=8，则m=2*8-1=15，按上述 算法可构造一棵Huffman树，如下左图和右图分别Hu
13、ffman树的初始 状态和终止状态。weightparentlchildrchild15000 229000 37000 48000 514000 623000 73000 811000900010000 11000 12000 13000 14000 15000weightparentlchildrchild15900 2291400 371000 481000 5141200 6231300 73900 8111100 981117 10151234 11191389 122914510 134215611 145815214 1510001314HT初始状态HT终止状态113581923
14、42291487152958100 01000011100111HC 1 0110 2 10 3 11104 1111 5 110 6 00 7 0111 8 011 Huffman编码Huffman树 3. 树的遍历 遍历：按一定搜索路经走遍树的各个顶点，使树中每一结点均被且仅被访问一次。 目的：产生树中所有结点的一个线性排列。 常用方法： 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树。 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点。 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，直到最后一层的结点。ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEF I GCDHJ KLNOMEIFGB CJKN OLMHD AAB CDE FGH I J KL MNO例6.16 树的遍历ABCDEFGHIJ例6.17 森林遍历先序遍历结果：A B C D E F G H I J中序遍历结果：B C D A F E H J I G
