例题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，所以结点总数 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-1 D. 2k例题6.2 写出如图6.2所示的二叉树的前(先)序中序和后序遍历序列. 解： 前序为“根左右”，从左到右收集的前序序列为：fdbacegihj； 中序为“左根右”，从左到右收集的中序序列为：abcdefghij； 后序为“左右根”，从左到右收集的后序序列为：acbedhjigf。fdgibehjac练习 一棵二叉树如图所示：写出对此树的先根 、中跟、后跟序列。 先根序列:ABDEFC 中根序列:DEFBAC 后根序列:FEDBCA已知先序和中序求后序 先序：ABCDEFGH 中序：BDCEAFHG 后序：已知中序和后序求先序 中序：BDCEAFHG 后序：DECBHGFA 求先序：问题 已知先序和后序能求中序么?例题6.3 若一棵二叉树，左右子树均有三个结点，其左子树的前（先） 序序列与中序序列相同，右子树的中序序列与后序序列相同，试构 造该树。 【解】据题意，左子树的前序序列与中序序列相同，即有：前序： 根 左 右中序： 左 根 右也即，以左子树为根的树无左孩子。此处，右子树的中序序列与后序 序列相同，即有：中序： 左 根 右后序： 左 右 根也即，以右子树为根的树无右孩子。由此构造该树如下图所示。例题4 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二 叉树的形状。 解：先序遍历为“根左右”，后序遍历为“左右根”。 根结点在两个序列中的位置分别在最前和最后，正好相反；因此，若要 两个序列正好相反，则左右子树必有一个不存在。其先序序列和后序序 列正好相反的二叉树必为单支树。即这棵二叉树的形状如下图所示 。 例题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=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层的父结点 为381/2=191，而第9层的其余结点也是叶结点，即29-1=256，256- 191=65，故第9层共有65个叶结点，则第10层叶结点+第9层叶结点 =381+65=446。例题6.6 对如下图所示的二叉树: 写出对它们进行先序 中序和后序遍历时得到的结点序列; 画出它们的先序线索二叉树和后序线索二叉树。【解】 对图进行先序中序和后序遍历时得到的 结点序列分别如下: 先序遍历的结点序列为：ABDFGHIEC 中序遍历的结点序列为：FDHGIBEAC 后序遍历的结点序列为：FHIGDEBCAABCGDEHIF二叉树的先序线索二叉树如下左图所示，后序线索二叉树如下右图所示。ABCGDEHIFNIL先序线索二叉树ABCGDEHIF后序线索二叉树NIL例题6.7 如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和 BDCAIFJGHE，请画出该森林。 【解】由于森林的前序序列与其对应的二叉树前序序列相同，而森林的 后序序列与其对应的二叉树中序序列相同。因此，根据二叉树前序序 列ABCDEFIGJH和中序序列BDCAIFJGHE可画出二叉树如下图所示。ABEDCGJIFH而由二叉树转化为森林的步骤得到对应的森林。ABDCEGJIFH例题6.8 证明n0个叶子结点的哈夫曼树共有2n0-1个结点。证明：设度为1和2的结点个数分别为n1和 n2，二叉树结点总数为n，则 有：n=n0+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 用孩子兄弟表示法表示下图所示的树(重点掌握)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.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树；然后将树中结点指向其左孩子的 分支标“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树，如下左图和右图分别Huffman树的初始 状态和终止状态。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终止状态11358192342291487152958100 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