当前位置：首页 > ops >正文

数据结构：二叉树的高度 (Height)和节点总数 (Count of Nodes)

ops 2025/8/19 15:55:16

二叉树的高度 (Height)

问题的起点：什么是“高度”？

从最简单的情况开始

寻找递归关系：一个大问题和子问题的关联

将逻辑翻译为代码

二叉树的节点总数 (Count of Nodes)

问题的起点：什么是“节点总数”？

寻找递归关系

二叉树的叶子节点数 (Count of Leaf Nodes)

问题的起点：什么是“叶子节点”？

寻找递归关系

完整代码与验证

我们继续用第一性原理来推导关于树的“度量”问题——高度和节点计数。

这些问题是递归思想最经典、最直观的应用。核心的推导思路是：“一个大问题的答案，可以由几个规模更小的、同类子问题的答案组合而成。”

二叉树的高度 (Height)

问题的起点：什么是“高度”？

首先，我们要给“高度”一个清晰、无歧义的定义。想象一下树是一座公司的组织架构图，根节点是CEO。

高度 (Height)： 从CEO (根节点) 到离他最远的基层员工 (最远的叶子节点) 需要经过多少个“管理层级”（即边的数量）。
一个节点的深度 (Depth): 从CEO到这个员工要经过多少层级。

我们通常关心的是整个树的高度。按照惯例，我们定义：

一棵只有一个节点的树，高度为 0 (因为从根到叶子没有需要跨越的边)。
一棵空树 (NULL)，我们约定其高度为 -1。这个约定非常巧妙，后面你会看到它如何让我们的计算公式变得完美。

从最简单的情况开始

最简单情况1：空树

height(NULL) -> 按约定，返回 -1。这是我们递归的第一个“出口”（Base Case）。

最简单情况2：只有一个节点的树

它的左右子树都是 NULL。如果我们知道它左右子树的高度（都是-1），能否推导出当前树的高度？

寻找递归关系：一个大问题和子问题的关联

让我们来看一棵更复杂的树，它有一个根节点 D，一个左子树 L 和一个右子树 R。

这棵完整树的高度是什么？

最长的路径，必然是“从根节点 D 出发，向下走一步，然后继续在某个子树里走完最长的路径”。
它要么是 1(D->L) + L的高度，要么是 1(D->R) + R的高度。
为了求得整棵树的最大高度，我们自然要选择两者中较大的那一个。

第一性推导结论 (递归公式)：

height(T) = 1 + max(height(T的左子树), height(T的右子树))

现在我们用这个公式来验证一下我们之前定义的简单情况：

对于只有一个节点的树：

height(root) = 1 + max(height(NULL), height(NULL))
height(root) = 1 + max(-1, -1)
height(root) = 1 + (-1) = 0
结果完全正确！约定高度为-1让我们的公式无需任何特殊处理就能完美工作。

将逻辑翻译为代码

我们需要一个函数 int height(Node* root)。

// 计算二叉树的高度
int height(Node* root) {// 1. 定义递归出口 (Base Case)// 根据我们的推导，最简单的情况是空树if (root == NULL) {return -1; // 返回-1，让公式完美运作}// 如果程序能走到这里，说明 root 不是 NULL。// 我们需要先知道其左右子树的高度，才能计算当前树的高度。// 2. 分解成子问题：递归计算左子树的高度int leftHeight = height(root->left);// 3. 分解成子问题：递归计算右子树的高度int rightHeight = height(root->right);// 4. 组合子问题的答案：应用我们的公式// 找出左右子树中较高的那个int maxHeight = (leftHeight > rightHeight) ? leftHeight : rightHeight;// 加上从当前节点到子树的那条边 (1)return 1 + maxHeight;
}

这段代码就是我们推导出的递归公式的直接翻译，非常清晰。

二叉树的节点总数 (Count of Nodes)

问题的起点：什么是“节点总数”？

这个问题很直观，就是数一数树里一共有多少个圈圈（节点）。

从最简单的情况开始

最简单情况1：空树 (NULL) 一个节点都没有，所以数量是 0。这是我们的递归出口。
最简单情况2：只有一个节点的树 数量显然是 1。

寻找递归关系

对于一个以 R 为根的非空树 T，它的总节点数等于什么？这个关系非常简单，甚至比高度更容易想到：

根节点 R 本身（这算 1 个）。
加上它左子树 L 的全部节点数。
加上它右子树 R 的全部节点数。

第一性推导结论 (递归公式)：

countNodes(T) = 1 + countNodes(T的左子树) + countNodes(T的右子树)

我们验证一下：

对于只有一个节点的树：

countNodes(root) = 1 + countNodes(NULL) + countNodes(NULL)
countNodes(root) = 1 + 0 + 0 = 1
结果完全正确！

将逻辑翻译为代码

// 计算二叉树的节点总数
int countNodes(Node* root) {// 1. 定义递归出口 (Base Case)if (root == NULL) {return 0;}// 2. 根据公式，直接组合子问题的答案// 1 (当前节点) + 左子树节点数 + 右子树节点数return 1 + countNodes(root->left) + countNodes(root->right);
}

二叉树的叶子节点数 (Count of Leaf Nodes)

问题的起点：什么是“叶子节点”？

叶子节点 (Leaf Node) 是指没有任何子节点的节点。也就是说，它的 left 指针和 right 指针都是 NULL。

从最简单的情况开始

最简单情况1：空树 (NULL)

没有节点，当然也就没有叶子节点。数量是 0。这是递归出口之一。

最简单情况2：只有一个节点的树

这个节点左右指针都是NULL，所以它是一个叶子节点。数量是 1。这是递归出口之二。

寻找递归关系

对于一个以 R 为根的树 T：

我们首先要判断一下，R 本身是不是一个叶子节点？
- if (root->left == NULL && root->right == NULL)
- 如果是，那么这棵树（此时就是单节点树）的叶子节点数就是 1。我们不需要再往下递归了。
如果 R 不是一个叶子节点（它至少有一个孩子）：
- 那么它自己对“叶子节点总数”的贡献是 0。
- 这棵树的叶子节点，必然全部隐藏在它的左子树或右子树中。
- 所以，总的叶子节点数就是左子树的叶子数 + 右子树的叶子数。

第一性推导结论 (递归公式)：

if T is NULL, return 0

if T的左右孩子都为NULL, return 1

else, return countLeaves(T的左子树) + countLeaves(T的右子树)

将逻辑翻译为代码

// 计算二叉树的叶子节点数
int countLeafNodes(Node* root) {// 1. Base Case 1: 空树没有叶子if (root == NULL) {return 0;}// 2. Base Case 2: 当前节点就是叶子节点if (root->left == NULL && root->right == NULL) {return 1; // 找到了一个叶子！}// 3. 递归步骤：如果当前不是叶子，则叶子在其子树中// 将左子树找到的叶子数和右子树找到的叶子数相加return countLeafNodes(root->left) + countLeafNodes(root->right);
}

完整代码与验证

我们把这些函数放到一个完整的程序里，用我们熟悉的示例树来验证一下。

#include <stdio.h>
#include <stdlib.h>// --- 节点定义和树的创建 (复用之前的代码) ---
typedef struct Node {char data;struct Node* left;struct Node* right;
} Node;Node* createNode(char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}Node* build_example_tree() {Node* root = createNode('A');root->left = createNode('B');root->right = createNode('C');root->left->left = createNode('D');root->left->right = createNode('E');root->right->right = createNode('F');/*A/ \B   C/ \   \D   E   F*/return root;
}// --- 我们刚刚推导出的三个函数 ---// 1. 计算高度
int height(Node* root) {if (root == NULL) {return -1;}int leftHeight = height(root->left);int rightHeight = height(root->right);return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
}// 2. 计算节点总数
int countNodes(Node* root) {if (root == NULL) {return 0;}return 1 + countNodes(root->left) + countNodes(root->right);
}// 3. 计算叶子节点数
int countLeafNodes(Node* root) {if (root == NULL) {return 0;}if (root->left == NULL && root->right == NULL) {return 1;}return countLeafNodes(root->left) + countLeafNodes(root->right);
}// --- Main 函数 ---
int main() {Node* root = build_example_tree();int treeHeight = height(root);printf("Height of the tree is: %d\n", treeHeight); // 预期: 2int totalNodes = countNodes(root);printf("Total number of nodes is: %d\n", totalNodes); // 预期: 6int leafNodes = countLeafNodes(root);printf("Number of leaf nodes is: %d\n", leafNodes); // 预期: 3 (D, E, F)return 0;
}

总结一下我们的推导过程： 对于每一个问题，我们都严格遵循了：