数据结构（Java语言版）-习题及答案 第7章树和二叉树习题答案

第7章树和二叉树习题参考答案 一、单选题ABCD现有一"遗传ABCD数组树图线性表ABCD一棵高度为h、结点个数为n的（≥ABCDnhn+hn-1h-1ABCDABCD581011ABCD一棵度为5、结点个数为n的ABCD5n4n+14n4n-1ABCABCD二叉树中每个结点的度均为2二叉树中至少有一个结点的度为2二叉树中每个结点的度可以小于2二叉树中至少有一个结点ABCD若一棵有nABCDn(k-1)/kn-kC.n+/k.nkn+/kABCD若一棵二叉树具有10个度为2的结点，5个度为1的结点，ABCD91115不确定ABCDABCD891011ABCDABCD16181231ABCABCD35163334AB高度为5的二叉树至多有 个结点。AB1632CDCD10ABCDABCD56731ABCD二叉树第iABCDi1C.1.1ABCABCD1110C.～5.～4ABCDABCD.1.2C.1.2ABCDABCD.1.2C.1.2ABCABCD6364C.7.8ABCABCD6364C.7.8ABCABCD636465不确定ABCABCD6465C.7.8设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是 。AABCD15717A如果一棵二叉树B是由一棵树T转换而来的二叉树，那么T中结点的先根序列对应B的 序列。 A先序遍历BBCD后序遍历层次遍历ABCD设一棵二叉树B是由森林T转换而来的，若T中有n个非叶子结点，则二叉树B中无ABCDn-1nn+1n+2ABCD某二叉树ABCD空或只有一个结点完全二叉树二叉排序树高度等于其结点数ABCD一棵二叉树的先序序列为ABCDEFG，它ABCDCABDEFGABCDEFGDACEFBGADCFEGBABCD一棵二叉树的先序遍历序列为ABCDEF，ABCDCBEFDAFEDCBACBEDFA不确定<gye="xdh:%;"rc="hp://cdnqngnene/bcedpng"/>ABCD由含n个结点的二叉树线索化后有 ABCD2nn+1n-12n-1A若x是中序线索二叉树中一个有左孩子的结点，且不是根结点，则x的前驱结点为 。 AB点BC点CD点D点ABCABCD99.0C.1.9ABCABCD.，，，，1.，，，，1C.，，，，1.，，，，1ABCABCD二叉树遍历就是访问二叉树中所有的结点二叉树遍历就是访问二叉树中部分结点二叉树遍历就是按照某种规律访问二叉树中所有的结点，且每个结点仅访问一次二叉树遍历就是随机访问二叉树中所有的结点，且每个结点仅访问一次ABC以下关于二叉树遍历的说法中，错误的是（ABC一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则先序和后序序列相同一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则中序和后序序列相同一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则先序和层次序列相同D一棵二叉树中，若每个结点最多只有右孩子，没有左孩子，则先序和中序序列相同DABCABCD若某结点是二叉树中某个子树的中序序列的最后一个结点，则它一定是该子树先序序列的最后一个结点若某结点是二叉树中某个子树的先序序列的最后一个结点，则它一定是该子树中序序列的最后一个结点若一个叶子结点是二叉树中某个子树的中序序列的最后一个结点，则它一定是该子树先序序列的最后一个结点若一个叶子结点是二叉树中某个子树的先序序列的最后一个结点，则它一定是该子树中序序列的最后一个结点ABCABCD先序遍历二叉树中序遍历二叉树层次遍历二叉树根据结点的值查找其存储位置给定二叉树如图所示。设N代表二叉树的根，代表根结点的左子树，代表根结点的右子树。若遍历后的结点序列为，则其遍历方式是 。AABCDLRNNRLRLNRNLABCABCD二叉树中每个结点的度均为2二叉树中至少有一个结点的度为2二叉树中每个结点的度可以小于2二叉树中至少有一个结点ABCABCD二叉树就是度为2的树二叉树中不存在度大于2的结点二叉树就是有序树二叉树中每个结点的度都为2ABCABCD二叉树中度为0的结点个数等于度为2的结点个数加1二叉树中结点个数必大于0完全二叉树中任何结点的度为0或2二叉树的度为2ABCABCD3456二叉树中所有结点的度之和等于结点数加（）。AABCD01-12ABCABCD有序数据元素无序数据元素元素之间具有分支层次关系的数据元素之间无联系的数据ABCD现有一“遗传ABCD数组树图线性表树是结点的有限集合，它（）根结点，记为。其余的结点分成为（≥）个互不相交的集合、、…、，每个集合又都是树，此时结点称为的双亲结点，称为的子树（≤≤）。一个结点的子树个数为该结点的次数（或度）。AABCD有0个或1个有0个或多个有且只有1个有1个或1个以上树是结点的有限集合，它有个或个根结点，记为。其余的结点分成为（≥）个（）的集合、、…、，每个集合又都是树，此时结点称为的双亲结点，称为的子树（≤≤）。一个结点的子树个数为该结点的次数（或度）。AABCD互不相交允许相交允许叶结点相交允许树枝结点相交树是结点的有限集合，它有个或个根结点，记为。其余的结点分成为（≥）个互不相交的集合、、…、，每个集合又都是树，此时结点称为的双亲结点，称为的子树（≤≤）。一个结点的子树个数为该结点的（）。AABCD权维数次数（或度）序ABCABCD加快查找结点的前趋或后继结点的速度为了能在二叉树中方便插入和删除为了能方便找到双亲使二叉树的遍历结果唯一ABCABCD左孩子右孩子指针标识ABCABCD逻辑逻辑和存储物理线性ABCD如图（）所示的二叉树是由森林转换而来的二叉树，那么森林有（ABCD4567ABCABCD1ghh/2h设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是（）。AABCD15717二、编程题.1000ms，空间限制：32768K。问题描述：二叉树是一组有限的顶点，或者为空或者由根r和两个不相交的子二叉树组成，称为左右子树。有三种最重要的遍历结点方式，即先序、中序和后序遍历。令T为有根r和子树T1、T2的二叉树，在T的先序遍历中，先访问根r，然后先序遍历T1，最后先序遍历T2。在T的中序遍历中，先中序遍历T1，然后访问根r，最后中序遍历T2。在T的后序遍历中，先后序中遍历T1，然后后序遍历T2，最后访问r。现在给出一棵二叉树的先序遍历序列和中序遍历序列，试着找出它的后序遍历序列。输入格式：输入包含几个测试用例。每个测试用例的第一行包含一个整数n（1≤n≤1000），即二叉树的结点数，后面跟着两行，分别表示先序遍历序列和中序遍历序列，你可以假设它们唯一构造一棵二叉树。输出格式：对于每个测试用例，打印一行指定相应的后序遍历序列。答：prtvu*;prtvuScnner;csNde //二叉链中结点类{ntd; //数据元素值Ndechd; //指向左孩子结点Nderchd; //指向右孩子结pubcNde) //默认构造方法{chd=rchd=nu;}pubcNdentd) //重载构造方法{d=d;chd=rchd=nu;}}pubccsn{nlcntN=;cn]n=newnN;cntk; //nk为后序遍历序列pubccNdeCreenprennntn)//先序序列pre和中序序列n构造二叉链{reurnCreeprenn;}prvecNdeCreen]prentn]nntntn){BTNodet;ntdpk;fn<=)reurnnu;d=pre;=newNded; //创建二叉树结点其值为先序序列首元素p=; //p指向中序序列的开始元素hep<+n) //在中序序列中找等于d的位置k{fnp==d)brek; //在n中找到后退出循环p++; //p指向中序序列的下一个元}k=p; //确定根结点在n中的位置chd=Creepre+nk;//递归构造左子树rchd=Creepre+k+np+nk;//递归构造右子树returnt;}pubccvdOrderNder)//后序遍历产生ns{fr=nu){Orderrchd;Orderrrchd;nk=rd;k++;}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;n]pre=newnN;n]n=newnN;BTNoderoot;henhNex){n=nnexIn;rnt=;i<n;++)pre=nnexIn;rnt=;i<n;++)n=nnexIn;r=Creeprenn;k=;Orderr;rnt=;i<k;++)Syeuprnn+"";Syeuprnnnk;}}}.HDU1622—：2000ms，空间限制：65536K。问题描述：树是许多计算机科学领域的基础。目前最先进的并行计算机如hnkngchne#;C都是以胖树为基础的。计算机图形学中常用到四叉树和八叉树。此问题涉及构建和遍历二叉树。给定一系列二叉树，你要编写一个程序来输出每棵树的层次遍历序列。在该问题中，二叉树的每个结点包含一个正整数，并且所有二叉树的结点个数少于256。在树的层次遍历中，按从左到右的顺序输出一层的所有结点值，并且层次k的所有结点在层次k+的所有结点之前输出。例如，如图所示的一棵二叉树的层次遍历序列是，，，，，，，，。<gye="x-dh:%;"rc="hp://cdnqngnene/ebdcbbpng"/>在这个问题中，二叉树由（n，）对序列指定，其中n是结点值，是从根结点到该结点的路径，路径是和构成的序列，其中表示左分支，表示右分支。在图的树中，结点由（13，RL）指定，2结点由（2，LLR）指定。根结点由（5，）的每个结点都只给出一次值（所有结点值不重复），则认为该二叉树是完全指定的。输入格式：输入是如上所述的二叉树序列，序列中的每棵树由如上所述的若干（n，s）对组成，中间用空格分隔。每棵树中的最后一个是()，左右括号之间没有空格。所有结点都包含正整数，输入中的每棵树将包含至少一个结点和不超过256个结点。输入由文件结束终止。输出格式：对于输入中每个完全指定的二叉树，应输出该树的层次遍历序列。如果未完全指定，即树中的某个结点未给定值或结点被赋予多于一次的值，则应输出字符串"ntcpee"。答：prtvu*;prtvuScnner;csNde //二叉链中结点类{ntd; //数据元素值Ndechd;//指向左孩子结点Nderchd;//pubcNde//默认构造方法{chd=rchd=nu;}pubcNdentd) //重载构造方法{d=d;chd=rchd=nu;}}pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;Srng;ntncnk;beng; //BTNoderoot,p,q;nt]n=newn;henhNex){=nnex; //处理一个cn=; /计n个数g=rue;engh==2&chr=='&chr==){Syeuprnn"ntcpee";//本测试用例只有一个""cnnue;}r=newNde; //p=r;herue) //处理n){engh==2&chr==&chr==)break; //遇到结尾"()"，退出循环处理p=r; //g){r=;i<engh;++){chr==)//遇到L{pchd=nu)//左孩子结点已经建立p=pchd;//移到该左孩子结点ee //左孩子结点没有建立{q=newNde;pchd=q;//建立左孩子结点初始值均为p=q;}}eechr==)//遇到R{prchd=nu)//右孩子结点已经建立p=prchd;//移到该右孩子结点ee //右孩子结点没有建立{q=newNde;prchd=q;//建立左孩子结点初始值均为p=q;}}}}n=;rnt=;j<engh;++)//取结点整数值nfchr>='&chr)<=)n=n*+chr;pd==)pd=n; //置路径末尾的结点值为neeg=e; //出现重复结点值，错=nnex; //继续读入下一个n)cn++; //n个数增1}rd==) //处理完所有n后根结点没有值g=e;k=; //层次序列n的下标g) //处理所有n后，进行存储遍历{Queue<Nde>qu=newnkedt<Nde>;qu.offer(root); //根结点进队hequEpy //队不空循环{p=qup; //出队一个结点pd=) //有效的已经有值的结nk++=pd;//添加到n中pchd=nu) //有左孩子时querpchd;//左孩子进队列prchd=nu) //有右孩子时querprchd;//右孩子进队列}}k==cn1&g) //访问了全部结点，正确{r=;i<k;++) //Syeuprnn+"";Syeuprnnnk;}eeSyeuprnn"ntcpee";//错误}}}.OJ—二叉树问题时间限制：，空间限制：。问题描述：二叉树是计算机科学中常见的数据结构。在本问题中，我们将看到一棵非常大的二叉树，其中结点包含一对整数，树的构造如下：（1）根包含整数对（1，1）。（2）如果一个结点包含（a，b），则其左孩子结点包含（a+b，b），右孩子结点包含（a，a+b）。该问题是给定上述二叉树的某个结点的内容（a，b），假设你沿着最短的路径从树根行走到给定结点，你能否知道需要经过左孩子的个数（走左路步数）和右孩子的个数（走右路步数）。输入格式：第一行包含场景个数。每个场景由一行构成，包含两个整数和（≤，≤×^）的结点（，），你可以假设这是上述二叉树中的有效结点。输出格式：每个场景的输出都以"Scenro#:"的行开头，其中是从开始的场景编号。然后输出包含两个数字l和r的单行（用空格分隔），其中l和r分别表示从树根遍历到输入的结点需要经过左、右孩子的个数，在每个场景后输出一个空行。答：prtvu*;prtvuScnner;pubccsn{cntr;pubccvdrventntb){he=1||b=)//搜索到为止{==) //为，则只走右路{r+=b;//走右路步数为b到达)break;}b==) //为，则只走左路{+=;//走左路步数为到达)break;}>b) //>b时，先走左路{+=/b;=b*/b;}ee //<b时，先走右路{r+=b/;b=*b/;}}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntnb;n=nnexIn;rnt=;i<=n;++){=nnexIn;b=nnexIn;=r=;rveb;Syeuprnn"Scenro#"++":";Syeuprnn+""+r;Syeuprnn;}}}OJ—围栏修复问题时间限制：，空间限制：。问题描述：农夫约翰想修修牧场周围的一小部分篱笆，他测量围栏并发现他需要n块（≤n≤）木板，每块木板都有一个整数长度（≤≤）。然后，他购买了一块足够长的长板（即其长度为所有长度的总和）。约翰忽略了切口，当切割锯切时，木屑损失了额外的长度，你也应该忽略它。约翰遗憾地意识到他没有切割木头的锯子，所以他带上这个长板去农民唐的农场，礼貌地问他是否可以借用锯子。唐并没有向约翰免费提供锯子，而是向约翰收取n-1次切割的费用，切割一块木头的费用与其长度完全相同，如切割长度为21的木板需要21美分。唐让约翰决定切割木板的顺序和位置。请你帮助约翰确定切割成n块木板的最低费用。约翰知道他可以以各种不同的顺序切割木板，这将导致不同的费用，因为所得到的中间木板有不同的长度。输入格式：第1行是一个整数n，表示木板数量，第2～n+1行每行包含一个描述n-1次的最低费用。答：prtvng*;prtvu*;prjavuScnner;pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;rryQueue<neger>pq=newrryQueue<neger>;//定义优先队列（默认小根堆）ntnxb;henhNex){pqcer;n=nnexIn;rnt=;i<n;++)//输入n个木板长度并进队{x=nnexIn;pq.offer(x);}ngn=; //采用n类型会溢出hepqe>)//按哈夫曼树的方式求ns{=pqp;//出队ab=pqp;//出队bpqer+b;//将+b进队n+=+b;/计到ns}Syeuprnnn;//输出结果}}}.OJ—是否为一棵树问题时间限制：，空间限制：。问题描述：树是众所周知的数据结构，它是空的（nu，vd，nhng），或者是由满足以下特性的结点之间的有向边连接的一个或多个结点的集合：只有一个结点，称为根，没有有向边指向它；除根之外的每个结点都只有一个指向它的边，从根到每个结点有一个有向边序列。例如，如图所示的图，其中结点由圆圈表示，边由带箭头的线条表示。其中前两个是树，但最后一个不是。<gye="x-dh:%;"rc="hp://cdnqngnene/bcdbedpng"/>在本问题中，给出有向边连接的结点集合，对于每个数据，你要确定它是否满足树的定义。输入格式：输入包含多个测试用例，以一对负整数结束。每个测试用例包含一个边序列，以一对零结束。每个边由一对整数组成，第一个整数表示边的开始结点，第二个整数表示边的终点。结点编号始终大于零。输出描述：对于每个测试用例，显示"Casekistree."或者"Casekisnotatree."，其中k对应于测试用例编号（它们从1开始按顺序编号）。答：prtvng*;prtvu*;prtvuScnner;pubccsn{nlcntN=;cnpren=newnN+;//并查集存储结构cnrnk=newnN+;//存储结点的秩cnv=newnN+;//结点集合cntn=N; //结点个数pubccvdIn) //并查集初始{rnt=;i<=n;++){rnk=;}}pubccntFndntx) //查找x结点的根结点{x=prenx)prenx=Fndprenx;//路径压缩returnparent[x];}pubccvdnnntxnty)//x和y的两个集合的合并{ntntry=Fndy;frx==ry) //x和yreturn;rnkrx]<rnkry)prenrx=ry; //rx结点作为ryee{rnkrx==rnkry//秩相同，合并后rx的秩增1rnkrx++;prenry=rx; //ry结点作为rx的孩子}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntc=; //测试用例个数beng=e; //外循环是否结束herue) //外循环处理所有测试用{ntb;benO=rue; //In;rnt=;i<n;++) //初始化元素为v=;herue) //内循环处理一个测试用例{=nnexIn;b=nnexIn;==0&b==)brek;//一个测试用例输入结束==1&b==)//输入全部结束{g=rue;break;}v=;vb=;Fnd=Fndb)&O)//，b不属于同一个子集nnb;ee //，b属于同一个子集，肯定不是树{O=e;cnnue; //需要继续输入其他边}}g)brek; //ntnu=;rnt=;i<=n;++) //求根结点个数{fv==1&pren==)nu++;fO=e;}O)Syeuprn"Ce%dsaree\n"c;eeSyeuprn"Ce%dsntaree\n"c;c++;}}}三、填空题在二叉树中，指针p所指结点为叶子结点的条件是（）。 答：p>chd==NL&p>rchd==NL由二叉树的先序遍历序列和中序遍历序列，（）唯一确定该二叉树。 答：能够由二叉树的后序遍历序列和中序遍历序列，（）唯一确定该二叉树。 答：能够由二叉树的层次遍历序列和中序遍历序列，（）唯一确定该二叉树。 答：能够由二叉树的先序遍历序列和后序遍历序列，（）唯一确定该二叉树。 答：不能一棵二叉树中不存在度的结点。 答：大于2一棵二叉树中，某结点即便只有一个孩子结点，也需要指出该孩子结点。 答：是左孩子还是右孩子节点一棵含有50个结点的二叉树，它的最小高度是。 答：6一棵含有50个结点的二叉树，它的最大高度是。 答：50一棵含有65个结点的高度最大的二叉树，第10层有个结点。答：1题1：哈夫曼树是。 答：带权路径长度最小的二叉树题2：一棵哈夫曼树有32个叶子结点，则该树的总结点个数是。 答：63树中任意结点允许有孩子结点，除根结点外，其余结点双亲结点。 答：有零个或多个;有且仅有一个在一棵树中，A结点有3个兄弟结点，B结点是A结点的双亲结点，则B结点的度是。 答：4二叉树线索化实质是将二叉链中改为存放该结点前趋或后继结点的地址。 答：空指针域一棵左右子树均不空的二叉树在先序线索化（不带头结点的线索化），后，其空指针域有个。 答：1一棵树中两个兄弟a和b，转换成二叉树后，a、b之间的关系是。 答：双亲-右孩子一棵树中结点a的第一个孩子是结点b，转换成二叉树后，a、b之间的关系是。 答：双亲-左孩子四、判断题由二叉树某种遍历方式产生的结果是一个线性序列。 答：正确非空二叉树的先序序列的最后一个结点一定是叶子结点。 答：正确非空二叉树的后序序列的最后一个结点一定是叶子结点。 答：正确非空二叉树的中序序列的最后一个结点一定是叶子结点。 答：错误非空二叉树的中序序列的第一个结点一定是叶子结点。 答：错误n（n>）个结点的二叉树中至少有一个度为的结点。 答：错误二叉树就是度为的有序树。 答：错误二叉树中每个度为的结点的两棵子树都是有序的。 答：正确二叉树是一种特殊的树。 答：错误二叉树中每个结点至多有两个孩子结点，而一般树没有这种限制，所以二叉树是树的特殊情形。 答：错误哈夫曼树中没有度为的结点。 答：正确哈夫曼树是带权路径长度最短的二叉树，权值越大的结点离根结点越远。 答：错误哈夫曼树中结点个数可以偶数也可以是奇数。 答：错误树中元素之间是多对多的关系。 答：错误树中每个结点都有唯一的前趋结点。 答：错误16.将二叉树变为线索二叉树的过程称为线索化。 答：正确17.给定一棵树T，可以找到唯一的一棵二叉树B与之对应。 答：正确18.给定一棵树T，将其转换成二叉树B后，它们的结点个数相同。 答：正确五、简答题对于以为根结点的一棵二叉树，指出其先序遍历访问的第一个结点和最后一个结点各是什么？ 答：先序遍历访问的第一个结点就是根结点a。先序遍历按照根→左→右的次序遍历。对于任一个结点来说，如果有右孩子，则最后访问到该右孩子，如果没有右孩子只有左孩子，则最后访问到该左孩子，当且仅当它没有孩子时，才最后访问到该结点。由此，找先序序列最后一个访问结点的过程是：从根结点出发，不断走向其右孩子，当不再有右孩子时，若有左孩子，转向其左孩子，然后再不断走向其右孩子，依次类推，直到走到一个叶子结点，它就是先序序列最后一个访问结点。对于以为根结点的一棵二叉树，指出其中序遍历访问的第一个结点和最后一个结点各是什么？ 答：中序遍历访问的第一个结点就是根结点a的最左下结点。中序遍历访问的最后一个结点就是根结点a的最右下结点。对于以为根结点的一棵二叉树，指出其后序遍历访问的第一个结点和最后一个结点各是什么？ 答：后序遍历按照左→右→根的次序遍历。对于任一个结点来说，如果有左孩子，最先遍历左子树，如果有右孩子，再遍历右子树，最后访问根结点，由此，找后序序列第一个访问结点的过程是：从根结点出发，不断走向其左孩子，当不再有左孩子时，若有右孩子，转向其右孩子，然后再不断走向其左孩子，依次类推，直到走到一个叶子结点，它就是后序序列第一个访问结点。后序遍历访问的最后一个结点就是根结点a对于一棵非空二叉树，为什么只知道其先序序列和后序序列，还不能唯一确定该二叉树的形态？ 答：因为二叉树的先序序列和后序序列都只确定了根结点的信息，而不能确定左、右子树的信息（左、右子树的结点个数），所以不能唯一确定该二叉树的形态。若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？ 答：二叉树的先序序列是NLR，后序序列是LRN。要使NLR=LRN成立，则L和R均为空，所以满足条件的二叉树只有一个根结点。简述一棵度为的有序树与一棵二叉树的区别。 答：两者的区别是：一棵度为2的有序树至少有3个结点，而二叉树的结点个数可以为0、一棵度为2的有序树中，度为1的结点无需区别左右，而二叉树中度为1的结点必须区别左右。给出具有个结点的不同形态的二叉树。 答：是否存在这样的一棵二叉树，其结点总数为，其中只有度为和度为的结点？为什么？ 答：有n个结点并且高度为n的不同形态的二叉树个数是多少？ 答：含有个叶子结点的二叉树的最小高度是多少？ 答：如果一棵哈夫曼树有n个叶子结点，那么，树有多少个结点，要求给出求解过程。答：

一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0n2+1，即n2n0-1，则总结点数nn0+n=n。如果一棵哈夫曼树的高度为h（h>），问最少可以对几个字符进行编码？最多可以对几个字符进行编码？ 答：哈夫曼树中只有度为2和0的结点，高等为h的哈夫曼树中叶子结点最少的情况是，第1层只有一个根结点，第2~h层每层有2个结点，共计叶子结点个数为h。所以最少可以对h个字符进行编码。高度为h的哈夫曼树中叶子结点最多的情况是构成一颗满二叉树，叶子结点集中在第h层，共计叶子结点个数为。所以最多可以对个字符进行编码。如果一棵哈夫曼树有n个叶子结点，那么，树有多少个结点，要求给出求解过程。 答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0n2+1，即n2n0-1，则总结点数nn0+n=n。如果一棵哈夫曼树的高度为h（h>），问最少可以对几个字符进行编码？最多可以对几个字符进行编码？ 答：哈夫曼树中只有度为2和0的结点，高等为h的哈夫曼树中叶子结点最少的情况是，第1层只有一个根结点，第2~h层每层有2个结点，共计叶子结点个数为h。所以最