[已解决]关于二叉树的几个问题

柿子饼同学

下面三个问题不会解 , 求教

这个题我用公式的话都 249 了, 为什么是 B 呢

最佳答案

月排行榜 / 总排行榜

jhq999

2022-9-3 16:21:25

百度上搜的（树的度和结点数的关系）

1. 一个有用的小公式：树中结点数 = 总分叉数 +1。(这里的分叉数就是所有结点的度之和)
   
2. 
   
3. 1.设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？
   
4. 
   
5. 解：
   
6. 
   
7. 叶子的度数为0；那么设叶子数为x，则此树的总分叉数为1*4+2*2+3*1+4*1=15；
   
8. 此树的节点个数为16（此处涉及到一个公式;节点数=分叉数+1，由图形便可以观察出来）。
   
9. 又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等式：4+2+1+1+x=16；x=8为叶子数。

复制代码

对于不主动学习的我来说，回答别人问题自己也学习一遍

跳转到最佳答案楼层

jhq999

转一条：

1. 1. 首先看下完全二叉树的定义：
   
2. 
   
3.     一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
   
4. 
   
5. 
   
6. 
   
7. 2.一条规则：
   
8. 
   
9.    对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
   
10. 
    
11.   推导过程：
    
12. 
    
13.   n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数。
    
14. 
    
15.   则分支数=2n2+n1  (每个n2节点有2个分支，每个n1结点有1个分支)
    
16. 
    
17.   另外又有：分支数=n0+n1+n2-1   (每个结点上面对应一个分支，除了根节点上面没有分支)
    
18. 
    
19.   2n2+n1=n0+n1+n2-1  得  n0=n2+1
    
20. 
    
21. 3.假设n为完全二叉树的结点总数，则有：n=n0+n1+n2
    
22. 
    
23.   结合2的结论有：n0=(n-n1+1)/2
    
24. 
    
25. 4.由于n1=1或者0，则
    
26. 
    
27.   当n1=0时(即度为1的节点为0个时,此时n为奇数）或者n为奇数时
    
28.               n0= (n+1)/2;
    
29. 
    
30.   当n1=1时(即度为1的节点为1个时,此时n为偶数）或者n为偶数
    
31. 
    
32.              n0= n/2;

复制代码

所以最大是2*n0=248

傻眼貓咪

.

jhq999

第二个我想应该只有两种情况，一个是只有左子树，一个是只有右子树，共同点是只有一个叶子
还有一种情况是只有根节点

jhq999

百度上搜的（树的度和结点数的关系）

1. 一个有用的小公式：树中结点数 = 总分叉数 +1。(这里的分叉数就是所有结点的度之和)
   
2. 
   
3. 1.设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？
   
4. 
   
5. 解：
   
6. 
   
7. 叶子的度数为0；那么设叶子数为x，则此树的总分叉数为1*4+2*2+3*1+4*1=15；
   
8. 此树的节点个数为16（此处涉及到一个公式;节点数=分叉数+1，由图形便可以观察出来）。
   
9. 又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等式：4+2+1+1+x=16；x=8为叶子数。

复制代码

对于不主动学习的我来说，回答别人问题自己也学习一遍

柿子饼同学

jhq999 发表于 2022-9-3 16:21
百度上搜的（树的度和结点数的关系）

对于不主动学习的我来说，回答别人问题自己也学习一遍

谢谢回答 , 懂了