二叉树习题及答案.docx

《二叉树习题及答案.docx》由会员分享，可在线阅读，更多相关《二叉树习题及答案.docx（2页珍藏版）》请在第壹文秘上搜索。

1、1 .设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？1依据1二叉树的第i层至多有2-1）个结点：深度为k的二叉树至多有2k-1个结点（根结点的深度为1”这特性质：因为2八97V699V2707,所以这个完全二叉树的深度是10.前9层是一个满二叉树，这样的话，前九层的结点就有249-1=511个：而第九层的结点数是291）=256所以第十层的叶子结点数是699-511=188个：现在来算第九层的叶了结点个数。由于第十层的叶了结点是从第九层延长的，所以应当去掉第九层中还仃子树的结点。因为第十层有188个,所以应当去掉第九层中的18所2=94个:所以,第九层的叶子结点个数是256-9

2、4=162,加上第十层有188个，最终结果是350个2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2,并且版下面一届的结点（叶结点）都依次排列在该乂最左边的位置上，这样的二叉树为完全二叉树。比如图：完全二叉树除叶结点层外的全部结点数（叶结点层以上全部结点数）为奇数，此题中，699是奇数，叶结点层以上的全部结点数为保证是奇数，则叶结点数必是偶数，这样我们可以马上选出答案为B!假如完全二叉树的叶结点都排满/,则是满二叉树，易得满二叉树的叶结点数是其以上全部层结点数+1比如图：此题的其实是一棵满二叉树,我们依据以上性质,699+1=700,700/2=350,即叶结点数为350,叶结点

3、层以上全都结点数为350-1=319.3完全二叉树中，只存在度为2的结点和度为0的结点，而二叉树的性质中有一条是：n=n2+1.sn指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699n2=349:11O=35（）2 .在一棵二叉箱上第5层的结点数多是多少一棵二叉树，假如每个结点都是是满的，那么会满意2A（k-1）1所以第5层至多有2（5-1）=16个结点!3 .在深度为5的清二叉内中，叶子结点的个数为答案是16叶子结点就是没有后件的站点说白了就是：叉树的最终一层深度为K的二叉树最多有2k-1.个结点G多有2Nk-1）个结点所以此题最多有25-1.=31个结点最多有2N5-1

4、）=16个叶子结点4.某二叉树中度为2的结点有1个，则该二叉材中有几个叶子结点？结点的度是指树中每个结点具有的了树个数或并说是后继结点数。题中的度为2是说具有的2个子树的结点：二叉树有特性质：二叉树上叶子结点数等F度为2的结点数加1.5 .在澡度为7的清二叉用中，度为2的结点个数为多少，就是第一层只有一个节点，他有两个子节点，其次层有两个节点，他们也都有两个子节点以此类推，所以到第6层，就有2的5次方个节点，他们都有两个子节点她终第7层都没有子节点了，因为於深度为7的.所以就是1+2+4+8+16+32了2深度为1的时候有O个深度为2的时候有1个深度为3的时帔有3个深度为4的时候有7个深度为n

5、的时候有（2的n-1次方减1）个6 .一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为？假设n表示二叉树的全部结点数，n表示度为0的结点（叶子结点），n1表示度为1的结点，n2表示度为2的结点，由二叉树的性质有：n=n2+1已知n=70.则n2=n-1=69而n=n+n1+n2=70+80+69=219总结点数n=70+80+70T=2192解：对任一：叉树,假如其叶子结点为n,度为1的结点数为n1.,度为2的结点数为n2,则n=n2+1.:然后由n=n+n1.+n2即可得出。（n为结点总数）证明上一结论：由二叉树的特点可知，除了根结点外,全部的结点都是由一个父支引

6、出来的，因此分支数为=nT,而二叉树中的分支都是由度为1和度为2的结点发出的，因此有A=n1.2*n2,于是A=n-1.=n1.+2*n2,得到:n=n1.+2*n2+1.由与可得：n=n2+1.7 .某二叉材有5个度为2的结点和3个度为I的结点，则该二叉树共有几个结点?二叉树性质：终端结点（叶子节点）个数n=度为2的节点（有2个孩子）个数2+1即n=2+1所以本题有：叶子节点个数=5+1=6.度为1的结点个数=3.度为2的结点个数=5.所以总个数=63+5=H2对任何棵二叉利T,假如其终端结点数为n,度为2的结点数为n2,则n=2+1故叶子结点数（即度为。的结点）为5+1=6二叉树的结点数为n=n0+n1+2所以该二叉树的结点为：5+3+6=14