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

约定不等于承诺〃 2022-05-08 15:52 236阅读 0赞

### 文章目录 ###

*   *   *  结点个数
         *  叶子结点个数
         *  二叉树高度
         *  第K层几个结点

1.  二叉树的结点个数
2.  二叉树叶子结点个数
3.  二叉树第K层结点个数
4.  二叉树的高度

**在二叉树中，我们经常用到递归，再用递归的时候，经常会用到：递推公式，终止条件  
递推公式：如果左子树和右子树的结果都有了，按照这个二叉树有三个结点往下操作  
终止条件：递归一般都必须有终止条件，按照二叉树的五种基本形态考虑终止条件会比较简单一点  
最后就是要考虑递归函数中的参数会不会发生改变**

### 结点个数 ###

递推公式：左子树结点个数 + 右子树结点个数 + 1  
终止条件：空树返回0

int GetTreeSize(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return 0;
    		}
    		return GetTreeSize(root->left) + GetTreeSize(root->right) + 1;
    	}

### 叶子结点个数 ###

递推公式：左子树叶子结点 + 右子树叶子结点  
终止条件：空树返回0  
          如果一个结点左右孩子都为NULL，返回1

int GetLeafSize(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return 0;
    		}
    		if (root->left == NULL && root->right == NULL)
    		{ 
    			return 1;
    		}
    		return GetLeafSize(root->left) + GetLeafSize(root->right);
    	}

### 二叉树高度 ###

递推公式：MAX(左子树高度，右子树高度) + 1，就是较大值 + 1  
终止条件：空树，返回0

#define MAX(a, b) (a) > (b) ? (a) : (b)
    
    	int GetTreeHeight(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return 0;
    		}
    		int height1 = GetTreeHeight(root->left);
    		int height2 = GetTreeHeight(root->right);
    		return MAX(height1, height2) + 1;
    	}

### 第K层几个结点 ###

递推公式：左子树K层结点个数 + 右子树K层结点个数  
终止条件：空树，返回0  
          K== 1，返回1，表示只有一个结点，高度为1

int GetTreeKSize(BNode *root, int k)
    	{ 
    		assert(k > 0);
    		if (root == NULL)
    		{ 
    			return 0;
    		}
    		if (k == 1)
    		{ 
    			return 1;
    		}
    		return GetTreeKSize(root->left, k--) + GetTreeKSize(root->right, k--);
    	}

**在二叉树的相关操作中，一定要学会推递推公式和终止条件**