EB1-计算二叉树结点个数¶

代码实现¶

C
/**
 * 计算型：递归计算二叉树节点个数
 * 基本思想：树的节点数 = 左子树节点数 + 右子树节点数 + 1(根节点)
 * @param p 二叉树根节点指针
 * @return 节点总数
 */
int countNodes_Compute(BiTree p) {
    // 递归终止条件：如果节点为空，则节点数为0
    if (p == NULL) {
        return 0;
    } else {
        // 递归计算左子树节点数
        int n1 = countNodes_Compute(p->lchild);

        // 递归计算右子树节点数
        int n2 = countNodes_Compute(p->rchild);

        // 返回总节点数：左子树节点数 + 右子树节点数 + 1(当前节点)
        return n1 + n2 + 1;
    }
}

C
/**
 * 操作型：递归计算二叉树节点个数
 * 基本思想：通过引用参数传递计数器，在遍历过程中递增计数器
 * @param p 二叉树根节点指针
 * @param n 指向计数器的指针
 */
void countNodes_Operate(BiTree p, int* n) {
    // 递归终止条件：如果节点不为空，则进行计数
    if (p != NULL) {
        // 访问当前节点：计数器加1
        ++(*n);

        // 递归遍历左子树
        countNodes_Operate(p->lchild, n);

        // 递归遍历右子树
        countNodes_Operate(p->rchild, n);
    }
}

C
/**
 * 非递归实现：使用栈计算二叉树节点个数
 * @param root 二叉树根节点指针
 * @return 节点总数
 */
int countNodes_Iterative(BiTree root) {
    if (root == NULL) {
        return 0;
    }

    // 使用简单的栈结构
    BiTNode* stack[1000];  // 假设树的最大节点数不超过1000
    int top = -1;          // 栈顶指针
    int count = 0;         // 节点计数器

    // 将根节点压入栈
    stack[++top] = root;

    // 当栈不为空时继续遍历
    while (top >= 0) {
        // 弹出栈顶节点
        BiTNode* current = stack[top--];
        count++;  // 计数器加1

        // 将右子树压入栈（如果存在）
        if (current->rchild != NULL) {
            stack[++top] = current->rchild;
        }

        // 将左子树压入栈（如果存在）
        if (current->lchild != NULL) {
            stack[++top] = current->lchild;
        }
    }

    return count;
}

中文伪代码¶

计算型伪代码¶

Text Only

计算节点数_计算型(根节点)
开始
    如果 根节点为空 则
        返回 0
    否则
        左子树节点数 = 计算节点数_计算型(左子树)
        右子树节点数 = 计算节点数_计算型(右子树)
        返回 左子树节点数 + 右子树节点数 + 1
    结束如果
结束

操作型伪代码¶

Text Only

计算节点数_操作型(根节点, 计数器指针)
开始
    如果 根节点不为空 则
        计数器加1
        计算节点数_操作型(左子树, 计数器指针)
        计算节点数_操作型(右子树, 计数器指针)
    结束如果
结束

非递归型伪代码¶

Text Only

计算节点数_非递归(根节点)
开始
    如果 根节点为空 则
        返回 0
    结束如果

    创建栈
    将根节点压入栈
    初始化计数器为0

    当 栈不为空 时循环执行
        弹出栈顶节点
        计数器加1
        如果 右子树不为空 则
            将右子树压入栈
        结束如果
        如果 左子树不为空 则
            将左子树压入栈
        结束如果
    结束循环

    返回 计数器值
结束

Mermaid流程图¶

计算型流程图¶

flowchart TD
    A[开始] --> B{节点为空?}
    B -->|是| C[返回0]
    B -->|否| D[递归计算左子树节点数]
    D --> E[递归计算右子树节点数]
    E --> F[返回:左子树数+右子树数+1]
    F --> G[结束]
    C --> G

操作型流程图¶

flowchart TD
    A[开始] --> B{节点为空?}
    B -->|是| C[返回]
    B -->|否| D[计数器加1]
    D --> E[递归遍历左子树]
    E --> F[递归遍历右子树]
    F --> G[结束]
    C --> G

非递归型流程图¶

flowchart TD
    A[开始] --> B{根节点为空?}
    B -->|是| C[返回0]
    B -->|否| D[创建栈并压入根节点]
    D --> E[初始化计数器为0]
    E --> F{栈为空?}
    F -->|否| G[弹出节点并计数器加1]
    G --> H{右子树存在?}
    H -->|是| I[右子树入栈]
    H -->|否| J{左子树存在?}
    I --> J
    J -->|是| K[左子树入栈]
    J -->|否| F
    K --> F
    F -->|是| L[返回计数器值]
    C --> L

复杂度分析¶

时间复杂度¶

O(n)，其中n是二叉树中节点的个数
分析：无论哪种实现方式，都需要访问二叉树中的每个节点 exactly 一次
每个节点都会被处理一次，因此时间复杂度都是线性的

空间复杂度¶

O(h)，其中h是二叉树的高度
分析：空间复杂度主要由递归调用栈的深度决定
最好情况（完全平衡二叉树）：h = log₂(n)，空间复杂度为 O(log n)
最坏情况（退化为链表）：h = n，空间复杂度为 O(n)
平均情况：h ≈ log₂(n)，空间复杂度为 O(log n)

图示说明¶

假设有一个如下二叉树：

Text Only
1 2 3 4 5	`1 / \ 2 3 / \ 4 5`

计算型执行过程图示¶

Text Only

countNodes_Compute(1) 执行过程：

countNodes_Compute(1)
├── countNodes_Compute(2)
│   ├── countNodes_Compute(4) → 返回 1
│   ├── countNodes_Compute(5) → 返回 1
│   └── 返回 1+1+1=3
├── countNodes_Compute(3) → 返回 1
└── 返回 3+1+1=5

操作型执行过程图示¶

Text Only

countNodes_Operate(1, &n) 执行过程（假设n初始为0）：

调用 countNodes_Operate(1, &n)
├── n = 1
├── 调用 countNodes_Operate(2, &n)
│   ├── n = 2
│   ├── 调用 countNodes_Operate(4, &n)
│   │   ├── n = 3
│   │   └── 返回
│   └── 调用 countNodes_Operate(5, &n)
│       ├── n = 4
│       └── 返回
└── 调用 countNodes_Operate(3, &n)
    ├── n = 5
    └── 返回

相关知识点延伸¶

1. 两种实现方式的特点对比¶

特点	计算型	操作型	非递归型
返回值	直接返回结果	通过参数传递结果	直接返回结果
内存使用	递归栈	递归栈+额外参数	显式栈
代码简洁性	简洁	较复杂	中等
易于理解	高	中	中
扩展性	好	好	一般

2. 递归与非递归的选择¶

递归实现：代码简洁，易于理解，但可能存在栈溢出风险
非递归实现：避免栈溢出，但代码相对复杂

3. 其他统计方法¶

C
// 层序遍历统计（使用队列）
int countNodes_LevelOrder(BiTree root) {
    if (root == NULL) return 0;

    BiTNode* queue[1000];
    int front = 0, rear = 0;
    int count = 0;

    queue[rear++] = root;

    while (front < rear) {
        BiTNode* current = queue[front++];
        count++;

        if (current->lchild) queue[rear++] = current->lchild;
        if (current->rchild) queue[rear++] = current->rchild;
    }

    return count;
}

4. 实际应用场景¶

文件系统：统计目录中的文件和子目录数量
组织架构：统计部门员工总数
游戏开发：统计游戏场景中的对象数量
数据库：统计树形结构数据的记录数

5. 性能优化建议¶

对于大型树结构，考虑使用非递归实现避免栈溢出
可以在节点结构中添加节点计数字段，实现O(1)时间复杂度的查询
对于频繁查询的场景，可以使用缓存机制

这些节点计数算法是二叉树操作的基础，理解其原理对于掌握更复杂的树算法非常重要。在实际应用中，应根据具体需求选择合适的实现方式。