跳转至

EC22-统计顺序存储的二叉树中叶子节点的个数

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 函数 count：统计顺序存储的二叉树中叶子节点的个数
// 参数：
// A[] - 存储二叉树的一维数组
// i - 当前节点在数组中的索引位置
// N - 数组的总长度
int count(char A[], int i, int N) {
    // 递归终止条件1：索引超出数组范围 或 当前节点为空节点
    if (i >= N || A[i] == '#') {
        return 0;
    }

    // 判断当前节点是否为叶子节点
    // 叶子节点的条件：没有左子节点 且 没有右子节点
    if ((2 * i + 1 >= N || A[2 * i + 1] == '#') && 
        (2 * i + 2 >= N || A[2 * i + 2] == '#')) {
        return 1; // 是叶子节点，返回 1
    }

    // 递归统计左子树和右子树的叶子节点个数
    int n1 = count(A, 2 * i + 1, N); // 统计左子树叶子节点数
    int n2 = count(A, 2 * i + 2, N); // 统计右子树叶子节点数

    // 返回左右子树叶子节点数的总和
    return n1 + n2;
}

代码逻辑解析

1. 顺序存储的二叉树

  • 二叉树通过一维数组存储，节点按照层次遍历的顺序排列
  • 对于索引为 i 的节点：
  • 左子节点索引：2*i + 1
  • 右子节点索引：2*i + 2
  • 父节点索引：(i-1)/2（向下取整）
  • 空节点通常用特殊字符（如 '#'）表示

2. 叶子节点的定义

  • 叶子节点是指没有子节点的节点
  • 判断条件：左子节点为空 且 右子节点为空

3. 算法思路

  • 使用递归遍历二叉树
  • 对每个节点判断是否为叶子节点
  • 如果是叶子节点，返回 1；否则递归统计左右子树的叶子节点数

4. 递归过程

  • 递归终止条件：
  • 索引超出数组范围
  • 当前节点为空节点（用 '#' 表示）
  • 叶子节点判断：
  • 左子节点索引超出范围 或 左子节点为空
  • 右子节点索引超出范围 或 右子节点为空
  • 递归统计：统计左右子树的叶子节点数并求和

时间复杂度分析

1. 访问节点数

  • 每个数组元素最多被访问一次
  • 时间复杂度：O(N)，其中 N 是数组长度

2. 每次操作复杂度

  • 每次访问和判断操作都是 O(1)
  • 总时间复杂度：O(N)

空间复杂度分析

1. 额外空间使用

  • 只使用了常量级别的局部变量
  • 没有使用额外的数据结构

2. 递归调用栈空间

  • 递归深度取决于树的高度
  • 对于完全二叉树：O(log N)
  • 最坏情况（退化为链表）：O(N)

3. 总体空间复杂度

O(h)，其中 h 是树的高度 在最坏情况下为 O(N)

较难理解部分的说明

1. 叶子节点判断条件详解

C
1
2
3
4
5
6
7
8
9
// 判断左子节点是否为空
(2 * i + 1 >= N || A[2 * i + 1] == '#')

// 判断右子节点是否为空  
(2 * i + 2 >= N || A[2 * i + 2] == '#')

// 叶子节点：左右子节点都为空
if (左子节点为空 && 右子节点为空)
    return 1; // 是叶子节点

条件解释：

  • 2 * i + 1 >= N：左子节点索引超出数组范围
  • A[2 * i + 1] == '#'：左子节点位置存储的是空节点标记
  • 两个条件用 ||（或）连接，满足其一即表示左子节点为空

2. 图解说明

假设顺序存储的二叉树数组如下：

Text Only
1
2
索引:  0   1   2   3   4   5   6   7   8   9   10  11  12
数组: [A,  B,  C,  D,  #,  E,  F,  #,  #,  #,  #,  G,  #]

对应的二叉树结构：

Text Only
1
2
3
4
5
6
7
        A(0)           // 非叶子节点
       /     \
     B(1)     C(2)     // 非叶子节点
    /  \     /  \
  D(3)  #(4) E(5) F(6) // D,E,F 是叶子节点
  / \       / \   / \
 #(7)#(8)  #(9)#(10) G(11) #(12) // G 是叶子节点

叶子节点识别过程：

Text Only
1
2
3
4
5
6
7
节点 A(0): 左子 B(1)≠'#', 右子 C(2)≠'#' → 非叶子
节点 B(1): 左子 D(3)≠'#', 右子 #(4)='#' → 非叶子  
节点 C(2): 左子 E(5)≠'#', 右子 F(6)≠'#' → 非叶子
节点 D(3): 左子 #(7)='#', 右子 #(8)='#' → 叶子节点
节点 E(5): 左子 #(9)='#', 右子 #(10)='#' → 叶子节点
节点 F(6): 左子 G(11)≠'#', 右子 #(12)='#' → 非叶子
节点 G(11): 左子越界, 右子越界 → 叶子节点

总叶子节点数：3（D, E, G）

延伸知识点

1. 非递归版本 - 使用栈

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 非递归统计叶子节点数
int countIterative(char A[], int N) {
    if (N == 0 || A[0] == '#') return 0;

    int leafCount = 0;
    Stack* stack = createStack(); // 假设有栈实现
    push(stack, 0); // 从根节点开始

    while (!isEmpty(stack)) {
        int i = pop(stack);

        // 检查当前节点是否为空
        if (i >= N || A[i] == '#') continue;

        // 检查是否为叶子节点
        bool leftEmpty = (2 * i + 1 >= N || A[2 * i + 1] == '#');
        bool rightEmpty = (2 * i + 2 >= N || A[2 * i + 2] == '#');

        if (leftEmpty && rightEmpty) {
            leafCount++; // 是叶子节点
        } else {
            // 将子节点入栈
            if (2 * i + 2 < N && A[2 * i + 2] != '#') 
                push(stack, 2 * i + 2); // 右子节点
            if (2 * i + 1 < N && A[2 * i + 1] != '#') 
                push(stack, 2 * i + 1); // 左子节点
        }
    }

    return leafCount;
}

2. 相关统计函数

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 统计内部节点数（非叶子节点数）
int countInternalNodes(char A[], int i, int N) {
    if (i >= N || A[i] == '#') return 0;

    // 如果是叶子节点，不计入内部节点
    if ((2 * i + 1 >= N || A[2 * i + 1] == '#') && 
        (2 * i + 2 >= N || A[2 * i + 2] == '#')) {
        return 0;
    }

    // 当前节点是内部节点，加上左右子树的内部节点数
    return 1 + countInternalNodes(A, 2 * i + 1, N) + 
               countInternalNodes(A, 2 * i + 2, N);
}

// 统计树的高度
int getHeight(char A[], int i, int N) {
    if (i >= N || A[i] == '#') return 0;

    int leftHeight = getHeight(A, 2 * i + 1, N);
    int rightHeight = getHeight(A, 2 * i + 2, N);

    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

3. 完全二叉树的优化

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 对于完全二叉树的优化版本
int countLeavesCompleteTree(char A[], int N) {
    if (N == 0) return 0;

    // 完全二叉树的叶子节点都在最后几层
    int leafStart = (N - 1) / 2 + 1; // 叶子节点开始位置
    int leafCount = 0;

    for (int i = leafStart; i < N; i++) {
        if (A[i] != '#') {
            leafCount++;
        }
    }

    return leafCount;
}

4. 实际应用场景

  • 文件系统：统计目录树中的文件数量（文件相当于叶子节点）
  • 组织架构：统计组织中的基层员工数量
  • 决策树：统计决策树中的叶节点（决策结果）
  • 语法分析：统计语法树中的终结符节点
  • 网络拓扑：统计网络中的终端设备数量

5. 性能对比分析

方法 时间复杂度 空间复杂度 适用场景
递归版本 O(N) O(h) 通用，代码简洁
非递归版本 O(N) O(N) 避免栈溢出风险
完全二叉树优化 O(√N) O(1) 特定于完全二叉树

这种方法体现了递归分治和顺序存储结构特性利用的思想，是处理树形数据的经典算法之一。