树的叶子结点与完全二叉树结点计算方法

今天药忘吃喽~ 2022-04-03 02:28 319阅读 0赞

# 一：完全二叉树中结点问题 #

分析：

设叶子节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2

侧有

n0+n1+n2=n (1)

对于二叉树有：

n0=n2+1 (2)

由(1)(2) ==>

n0=(n+1-n1)/2 (3)

由完全二叉树的性质可知：n1=0 或 1

总结:

(a):当n1=0时(即度为1的节点为0个时,此时n为奇数）或者n为奇数时

n0= (n+1)/2;

(b):当n1=1时(即度为1的节点为1个时,此时n为偶数）或者n为偶数

n0= n/2;

综合(a)(b)可得：

(结论):一个具有n个节点的完全二叉树,其叶子节点的个数n0为: n/2 向上取整，或者(n+1)/2 向下取整

**首先定义二叉树的度为子节点的个数，因此根据这个概念，节点情况只有0，1，2三种情况，分别用n0,n1,n2表示。  
一个棵树的节点总数=n0+n1+n2  
如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70][]

**当节点数N为奇数时，说明该树结构中没有度为1的节点。  
当节点数为偶数时，说明有一个度为1的节点，如上图情况。  
对于一个非空二叉树，有以下等式成立  
n0=n2+1**

**举例说明：  
设一棵完全二叉树共有699个节点，则在该二叉树中的叶节点数是什么？  
n=n0+n1+n2  
n0=n2+1  
n=699，奇数，说明n1为0；  
n=n0+n0-1  
n0=350，所以叶节点数为350。**

**下面看另一个题目：**

**一颗完全二叉树第六层有8个叶结点（根为第一层），则结点个数最多有（）个。**

**二叉树第k层最多有 2^(k-1) 个节点  
第六层最多有32个节点  
第五层最多有16个节点  
第四层最多有8个节点  
第三层最多有4个节点  
第二层最多有2个节点  
第一层最多有1个节点**

**完全二叉树的叶节点只可能出现在后两层**

**如果完全二叉树有6层，则前5层是满二叉树，总节点数目为16+8+4+2+1+8=39**

**如果完全二叉树有7层，则前6层是满二叉树，  
前六层总节点数目为32+16+8+4+2+1=63  
第六层有8个叶子节点，则有32-8=24个非叶子节点  
第七层最多有24\*2个叶子节点  
总节点数目为63+24\*2=111**

# **二：树的叶子结点计算方法** #

**在学习树的时候经常会遇到计算树中叶子结点的个数的题，比如现在有这样一道题**

**已知在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点的个数为？  
解决这道题的思路是列出一个关于各个度的结点的等式，从而根据已知条件算出度为0的结点的个数，下面具体说一下解题方法：**

**设树T中的结点个数为n，度为0的结点的个数为n0，度为1的结点的个数为n1，度为2的结点的个数为n2，度为3的结点的个数为n3，度为4的结点的个数为n4，则有：**

**n = n0 + n1 + n2 + n3 + n4**

**设树T中的总边数为e，因为除了根节点的入度为0，其余各节点的入度都为1，则有：**

**e = n - 1 = n0 + n1 + n2 + n3 + n4 - 1**

**又因为，n0的出度为0，n1的出度为1，n2的出度为2，n3的出度为3，n4的出度为4，所以：**

**e = n0 \* 0 + n1 \* 1+ n2 \* 2 + n3 \* 3 + n4 \* 4**

**综上所述:**

**e = n0 \* 0 + n1 \* 1+ n2 \* 2 + n3 \* 3 + n4 \* 4 = n0 + n1 + n2 + n3 + n4 - 1**

**n0 = n2 + n3 \* 2 + n4 \* 3 + 1**

**根据题意，n2 = 1, n3 = 10 ,n4 = 20 ,代入得:**

**n0 = 82**

**因此该树T有82个叶子结点**

**看完了上面的解题过程，思路应该很清晰明了吧，没懂？没关系，我们再来看一道题**

**一棵度为3的树中，有3度的结点100个，有2度的结点200个，有叶子结点多少个？  
还是和上面一样的解题过程，我稍微简略一点写，思路都是一样的**

**n = n0 + n1 + n2 + n3**

**e = n - 1 = n0 + n1 + n2 + n3 - 1**

**e = n0 \* 0 + n1 \* 1 + n2 \* 2 + n3 \* 3**

**n0 + n1 + n2 + n3 - 1 = n0 \* 0 + n1 \* 1 + n2 \* 2 + n3 \* 3**

**n0 = n2 + n3 \* 2 + 1**

**则叶子结点的个数为401个**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70]: /images/20220403/4b86dd3b17494dcca3bc428edc9edeff.png

树的叶子结点与完全二叉树结点计算方法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 NOJ数据结构016——计算二叉树叶子结点数目

相关按先序打印二叉树叶子结点

相关树：求二叉树的高度和叶子结点数量

相关二叉树叶子结点计数

相关二叉树结点、叶子结点个数，高度，第K层几个结点

相关求二叉树中叶子结点的个数

相关求完全二叉树的结点个数

相关求二叉树中叶子结点的个数

相关二叉树结点

相关树的叶子结点与完全二叉树结点计算方法