关于二叉树的几个问题
下面三个问题不会解 , 求教这个题我用公式的话都 249 了, 为什么是 B 呢
本帖最后由 jhq999 于 2022-9-3 16:03 编辑
转一条：
1. 首先看下完全二叉树的定义：
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
2.一条规则：
对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
推导过程：
n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数。
则分支数=2n2+n1(每个n2节点有2个分支，每个n1结点有1个分支)
另外又有：分支数=n0+n1+n2-1 (每个结点上面对应一个分支，除了根节点上面没有分支)
2n2+n1=n0+n1+n2-1得n0=n2+1
3.假设n为完全二叉树的结点总数，则有：n=n0+n1+n2
结合2的结论有：n0=(n-n1+1)/2
4.由于n1=1或者0，则
当n1=0时(即度为1的节点为0个时,此时n为奇数）或者n为奇数时
n0= (n+1)/2;
当n1=1时(即度为1的节点为1个时,此时n为偶数）或者n为偶数
n0= n/2;
所以最大是2*n0=248 . 本帖最后由 jhq999 于 2022-9-3 16:34 编辑
第二个我想应该只有两种情况，一个是只有左子树，一个是只有右子树，共同点是只有一个叶子
还有一种情况是只有根节点 本帖最后由 jhq999 于 2022-9-3 16:30 编辑
百度上搜的（树的度和结点数的关系）
一个有用的小公式：树中结点数 = 总分叉数 +1。(这里的分叉数就是所有结点的度之和)
1.设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？
解：
叶子的度数为0；那么设叶子数为x，则此树的总分叉数为1*4+2*2+3*1+4*1=15；
此树的节点个数为16（此处涉及到一个公式;节点数=分叉数+1，由图形便可以观察出来）。
又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等式：4+2+1+1+x=16；x=8为叶子数。
对于不主动学习的我来说，回答别人问题自己也学习一遍{:5_108:} jhq999 发表于 2022-9-3 16:21
百度上搜的（树的度和结点数的关系）
对于不主动学习的我来说，回答别人问题自己也学习一遍
谢谢回答 , 懂了
页:
[1]