用C语言求二叉树的叶子结点总数的非递归算法
时间: 2024-12-19 22:24:45 浏览: 46
在C语言中,求解二叉树的叶子节点总数可以采用迭代而非递归的方式,通常我们会使用栈来辅助计算。以下是一个简单的非递归算法步骤:
1. 初始化两个变量:`count`用于存储叶子节点的数量,初始化为0;`current`用于当前访问的节点,初始设置为根节点。
2. 当`current`不为空时,做如下操作:
a. 如果`current`是叶子节点(即没有左孩子和右孩子的节点),则`count++`,然后将`current`设为其父节点(如果有的话)。
b. 否则,先将`current`的右孩子入栈,再将其左孩子入栈。这样保证了总是先处理左孩子,因为当我们处理完左孩子后,左孩子已经从栈顶移除,不会再次进入循环。
c. 重复这个过程,直到`current`变为NULL。
3. 当栈为空时,所有叶子节点都已经处理过,返回`count`作为结果。
以下是C语言代码实现的例子:
```c
#include <stdio.h>
#include <stdbool.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int countLeaves(TreeNode* root) {
if (!root) return 0; // 如果节点为空,则结束
stack<TreeNode*> s;
s.push(root); // 将根节点压入栈
while (!s.empty()) {
TreeNode* node = s.top(); s.pop();
if (!node->left && !node->right) { // 如果找到叶子节点
++countLeaves;
}
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
return countLeaves;
}
// 示例用法
int main() {
TreeNode* tree = ...; // 实例化并构建你的二叉树
int leafCount = countLeaves(tree);
printf("二叉树的叶子节点数为:%d\n", leafCount);
return 0;
}
阅读全文
相关推荐


















