树与二叉树典型例题讲解课件

例题例题6.16.1 已知一棵度为已知一棵度为m的树有的树有n1个度为个度为1的结点，的结点，n2个度为个度为2的结点，的结点，nmnm个为个为m m结点，问该树中有多少个叶子结点？结点，问该树中有多少个叶子结点？解：解：设设n n为总结点个数，为总结点个数，n0n0为叶子结点为叶子结点(即度为即度为0 0的结点个数的结点个数)，则有，则有:n=n0+n1+n2+n=n0+n1+n2+nm +nm (1)(1)又有（分支总数）：又有（分支总数）：n-1=n1*1+n2*2+n3*3+n-1=n1*1+n2*2+n3*3+nm*m +nm*m (2)(2)（因为一个结点对应一个分支）（因为一个结点对应一个分支）式式(2)-(1)(2)-(1)得得:1=n0-n2-2n3-1=n0-n2-2n3-(m-1)nm-(m-1)nm则有则有:n0=1+n2+2n3+:n0=1+n2+2n3+(m-1)nm+(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 Dll2、一棵具有 n个结点的完全二叉树的树高度（深度）是（）Alogn+1 Blogn+1 Clogn Dlogn-13、一棵树高为K的完全二叉树至少有（）个结点。A2k 1 B.2k-1 1 C.2k-1 D.2k例题例题6.2 6.2 写出如图写出如图6.26.2所示的二叉树的前所示的二叉树的前(先先)序序中序和后序遍历序列中序和后序遍历序列.解：解：前序为前序为“根左右根左右”，从左到右收集的前序序列为：，从左到右收集的前序序列为：fdbacegihjfdbacegihj；中序为中序为“左根右左根右”，从左到右收集的中序序列为：，从左到右收集的中序序列为：abcdefghijabcdefghij；后序为后序为“左右根左右根”，从左到右收集的后序序列为：，从左到右收集的后序序列为：acbedhjigfacbedhjigf。fdgibehjac练习一棵二叉树如图所示：写出对此树的先根、中跟、后跟序列。先根序列:ABDEFC中根序列:DEFBAC后根序列:FEDBCA已知先序和中序求后序先序：ABCDEFGH中序：BDCEAFHG后序：已知中序和后序求先序中序：BDCEAFHG后序：DECBHGFA求先序：问题已知先序和后序能求中序么?例题例题6.3 6.3 若一棵二叉树，左右子树均有三个结点，其左子树的前（先）若一棵二叉树，左右子树均有三个结点，其左子树的前（先）序序列与中序序列相同，右子树的中序序列与后序序列相同，试构序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。造该树。【解解】据题意，左子树的前序序列与中序序列相同，即有：据题意，左子树的前序序列与中序序列相同，即有：前序：前序：根根 左左 右右 中序：中序：左左 根根 右右 也即，以左子树为根的树无左孩子。此处，右子树的中序序列与后也即，以左子树为根的树无左孩子。此处，右子树的中序序列与后序序列相同，即有：序序列相同，即有：中序：中序：左左 根根 右右 后序：后序：左左 右右 根根 也即，以右子树为根的树无右孩子。由此构造该树如下图所示。也即，以右子树为根的树无右孩子。由此构造该树如下图所示。例题例题4 4 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。二叉树的形状。解：解：先序遍历为先序遍历为“根左右根左右”，后序遍历为，后序遍历为“左右根左右根”。根结点在两个序列中的位置分别在最前和最后，正好相反；因此，若要根结点在两个序列中的位置分别在最前和最后，正好相反；因此，若要两个序列正好相反，则左右子树必有一个不存在。其先序序列和后序序两个序列正好相反，则左右子树必有一个不存在。其先序序列和后序序列正好相反的二叉树必为单支树。即这棵二叉树的形状如下图所示列正好相反的二叉树必为单支树。即这棵二叉树的形状如下图所示 。例题例题6.5 已知一棵完全二叉树共有已知一棵完全二叉树共有892892个结点，试求：个结点，试求：树的高度；树的高度；叶结点数；叶结点数；单支单支(度为度为1)结点数；结点数；最后一个非终端结点的序号。最后一个非终端结点的序号。解：解：(1)(1)根据性质根据性质2，已知深度为，已知深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1)，由于：由于：29-1892 210-1，所以树的高度为，所以树的高度为10。(2)(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)(3)由由解过程可知解过程可知n1=1，单支结点数为，单支结点数为1。(4)(4)对有对有n个结点的完全二叉树，最后一个树叶结点，即序号为个结点的完全二叉树，最后一个树叶结点，即序号为n的叶的叶结点其双亲结点结点其双亲结点n/2n/2为最后一个非终端结点，则序号为为最后一个非终端结点，则序号为892/2=446892/2=446。此外，由此外，由可知：可知：n n2 2=445=445，n n1 1=1=1；则最后一个非终端结点的序号为；则最后一个非终端结点的序号为445+1=446445+1=446。对于对于还可以采用如下：因还可以采用如下：因892289229 9-1-1，则前，则前9 9层的结点数为层的结点数为2 29 9-1=511-1=511个；个；而第而第1010层的结点为层的结点为892-511=381892-511=381个，且个，且381381个结点对应第个结点对应第9 9层的父结点为层的父结点为381/2=191381/2=191，而第，而第9 9层的其余结点也是叶结点，即层的其余结点也是叶结点，即2 29-19-1=256=256，256-256-191=65191=65，故第，故第9 9层共有层共有6565个叶结点，则第个叶结点，则第1010层叶结点层叶结点+第第9 9层叶结点层叶结点=381+65=446=381+65=446。例题例题6.66.6 对如下图所示的二叉树对如下图所示的二叉树:写出对它们进行先序写出对它们进行先序中序和后序遍历时得到的结点序列中序和后序遍历时得到的结点序列;画出它们的先序线索二叉树和后序线索二叉树。画出它们的先序线索二叉树和后序线索二叉树。【解解】对图进行先序对图进行先序中序和后序遍历时得到的中序和后序遍历时得到的结点序列分别如下结点序列分别如下:先序遍历的结点序列为：先序遍历的结点序列为：ABDFGHIECABDFGHIEC中序遍历的结点序列为：中序遍历的结点序列为：FDHGIBEACFDHGIBEAC后序遍历的结点序列为：后序遍历的结点序列为：FHIGDEBCAFHIGDEBCAABCGDEHIF二叉树的先序线索二叉树如下左图所示，后序线索二叉树如下右图所示。二叉树的先序线索二叉树如下左图所示，后序线索二叉树如下右图所示。ABCGDEHIFNIL先序线索二叉树先序线索二叉树ABCGDEHIF后序线索二叉树后序线索二叉树NIL例题例题6.7 如果已知森林的前序序列和后序序列分别为如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和和BDCAIFJGHE，请画出该森林。，请画出该森林。【解解】由于森林的前序序列与其对应的二叉树前序序列相同，而森林的由于森林的前序序列与其对应的二叉树前序序列相同，而森林的后序序列与其对应的二叉树中序序列相同。因此，根据二叉树前序序后序序列与其对应的二叉树中序序列相同。因此，根据二叉树前序序列列ABCDEFIGJHABCDEFIGJH和中序序列和中序序列BDCAIFJGHEBDCAIFJGHE可画出二叉树如下图所示。可画出二叉树如下图所示。ABEDCGJIFH而由二叉树转化为森林的步骤得到对应的森林。而由二叉树转化为森林的步骤得到对应的森林。ABDCEGJIFH例题例题6.8 6.8 证明证明n0个叶子结点的哈夫曼树共有个叶子结点的哈夫曼树共有2 2n0-1-1个结点。个结点。证明：设度为证明：设度为1 1和和2 2的结点个数分别为的结点个数分别为n1和和 n2，二叉树结点总数为，二叉树结点总数为n n，则，则有：有：n=n=n0+n1+n2根据二叉树的性质知：根据二叉树的性质知：n0=n2+1+1此外，由哈夫曼树的构造原理可知：哈夫曼树不存在度为此外，由哈夫曼树的构造原理可知：哈夫曼树不存在度为1 1的结点，即的结点，即n1=0=0；所以由；所以由可得：可得：n=n0+0+n2=n0+n0-1=2n0-1abcdefhgi601234578 bdefghi cdatafc 1 2 3 4 8 67 5 aCTree.r=0CTree.n=9例例6.9 用孩子链表结构表示西图所示的树用孩子链表结构表示西图所示的树612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiPCTree.r=1PCTree.r=1PCTree.n=9PCTree.n=9例例6.10 用带双亲的孩子链表表示下图所示的树用带双亲的孩子链表表示下图所示的树例6.11 用孩子兄弟表示法表示下图所示的树(重点掌握)abcdefhgib d a c e f g h i与树对应的二叉树表示其根结与树对应的二叉树表示其根结点无右子树。点无右子树。（1）树与二叉树转换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释例6.12 森林、树与二叉树转换（以二叉链表为纽带）森林转换成二叉树森林转换成二叉树将各棵树分别转换成二叉树（根结点均无右孩子）；将各棵树分别转换成二叉树（根结点均无右孩子）；将各二叉树的根结点依次用分支线连起来；将各二叉树的根结点依次用分支线连起来；以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。构成二叉树型结构。森林转化成二叉树的过程森林转化成二叉树的过程:ABCDEFGHIJ森林森林ABCDEFGHIJ对应二叉树对应二叉树ABCDEFGHIJABCDEFGHIJ连接跟结点连接跟结点旋转成二叉树旋转成二叉树例例6.13 6.13 二叉树转换成森林二叉树转换成森林抹线抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树间连线全部抹掉，使之变成孤立的二叉树还原还原：将孤立的二叉树还原成树：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ例例6.14 Huffman6.14 Huffman编码设计实例编码设计实例已知某系统在通信联络中只可能出现已知某系统在通信联络中只可能出现8 8种字符，其概率分别为种字符，其概率分别为0.050.05，0.290.29，0.070.07，0.080.08，0.140.14，0.230.23，0.030.03，0.110.11，试设计，试设计HuffmanHuffman编码。编码。解一：解一：先构造先构造HuffmanHuffman树，再进行编码。树，再进行编码。HuffmanHuffman编码实现过程：编码实现过程：以报文所用的不同字符为叶结点，以字符出以报文所用的不同字符为叶结点，以字符出现频率为权重构造现频率为权重构造HuffmanHuffman树树；然后将树中结点然后将树中结点指向指向其左孩子的分支其左孩子的分支标标“0 0”，指向指向其右孩子的分支标其右孩子的分支标“1 1”；每个字符的编码即为从根到；每个字符的编码即为从根到每个叶子每个叶子（字符）（字符）的路径上得到的的路径上得到的0 0、1 1序列序列。这种对字符的编码就是。这种对字符的编码就是HuffmanHuffman编码。编码。1135819234229148715295810001000011100111 HC 1 01102 10 3 11104 11115 110 6 00 7 01118 011 HuffmanHuffman编码编码HuffmanHuffman树树解二：解二：利用利用HuffmanHuffman编码算法实现。根据题意，取编码算法实现。根据题意，取8 8个字符的权分别为（个字符的权分别为（5 5，2929，7 7，8 8，1414，2323，3 3，1111），），n=8n=8，则，则m=2*8-1=15m=2*8-1=15，按上述算法可，按上述算法可构造一棵构造一棵HuffmanHuffman树，如下左图和右图分别树，如下左图和右图分别HuffmanHuffman树的初始状态和终树的初始状态和终止状态。止状态。weightparentlchildrchild150002290003700048000514000623000730008110009000100001100012000130001400015000 weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152141510001314HTHT初始状态初始状态HTHT终止状态终止状态1135819234229148715295810001000011100111 HC 1 01102 10 3 11104 11115 110 6 00 7 01118 011 HuffmanHuffman编码编码HuffmanHuffman树树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 JA B C D E F G H I J中序遍历结果：中序遍历结果：B C D A F E H J I GB C D A F E H J I G