首页统计二叉树结点个数

统计二叉树结点个数

时间: 2025-05-29 19:27:55 浏览: 30

### 实现统计二叉树结点个数的算法为了实现统计二叉树结点个数的功能，可以采用递归的方式完成。以下是基于 C 语言的具体实现： #### 算法说明通过递归遍历整棵二叉树来统计节点数量。如果当前节点为空，则返回 0；否则分别递归计算其左子树和右子树的节点数目，并加上当前节点的数量。 #### 完整代码实现 ```c #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 创建二叉树（此处省略具体实现） BiTree Create(); // 统计二叉树结点个数的核心函数 int NodeCount(BiTree T) { if (T == NULL) { // 如果树为空，返回0 return 0; } int leftCount = NodeCount(T->lchild); // 计算左子树的结点数 int rightCount = NodeCount(T->rchild); // 计算右子树的结点数 return leftCount + rightCount + 1; // 当前结点加左右子树的总和 } int main() { BiTree T = Create(); // 假设已经创建好了一棵树 printf("%d\n", NodeCount(T)); // 输出结点总数 return 0; } ``` 此代码实现了 `NodeCount` 函数用于统计二叉树中的结点个数[^1]。当传入的树为空时，直接返回 0；否则递归调用自身处理左子树和右子树，并最终累加得到整个树的结点总数。 #### 关键逻辑解释 - **递归终止条件**：当遇到空指针时停止递归并返回 0。 - **递归过程**：每次递归都分解成更小的部分，即左子树和右子树的结点数之和再加上当前结点本身。这种方法的时间复杂度为 O(n)，其中 n 是二叉树中结点的总数，因为每个结点都会被访问一次[^3]。 --- ###

阅读全文