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

柿子饼同学

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

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

最佳答案

月排行榜 / 总排行榜

jhq999

2022-9-3 16:21:25

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

一个有用的小公式：树中结点数 = 总分叉数 +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为叶子数。

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

跳转到最佳答案楼层

jhq999

转一条：

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

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

jhq999

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

一个有用的小公式：树中结点数 = 总分叉数 +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为叶子数。

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

柿子饼同学

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

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

谢谢回答 , 懂了