首页用C语言对二叉树进行非递归中序遍历并统计叶子结点数量。假定二叉树已经存在。

用C语言对二叉树进行非递归中序遍历并统计叶子结点数量。假定二叉树已经存在。

时间: 2024-12-01 17:30:34 浏览: 45

在C语言中，对二叉树进行非递归中序遍历，并统计叶子节点数量，可以使用栈的数据结构来辅助实现。以下是步骤： 1. 定义一个函数`isLeaf(node)`判断给定节点是否为叶子节点（即无左孩子和右孩子的节点）。 2. 创建一个`void inorderTraversal(node*, int count)`函数，它接收当前节点和一个计数器作为参数。开始时将根节点压入栈中。 3. 当栈不为空时，进行循环： a. 弹出栈顶元素，访问当前节点（如果是叶节点，计数器加一）。 b. 如果当前节点有右孩子，将右孩子压入栈中。 c. 如果当前节点有左孩子，说明还没访问完左子树，先将其左孩子压入栈。 4. 遍历结束后返回计数器，即为叶子节点的数量。下面是一个简单的示例代码实现： ```c #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; int isLeaf(TreeNode* node) { return !node->left && !node->right; } void inorderTraversal(TreeNode* root, int* leafCount) { if (!root) return; TreeNode* stack[100]; int top = -1; stack[++top] = root; while (top != -1) { TreeNode* current = stack[top--]; // 访问节点 printf("%d ", current->val); // 将右子节点压入栈 if (current->right) stack[++top] = current->right; // 先处理左子节点 if (current->left) stack[++top] = current->left; // 叶子节点计数 if (isLeaf(current)) (*leafCount)++; } } // 主函数测试 int main() { TreeNode* root = ...; // 初始化二叉树 int leafCount = 0; inorderTraversal(root, &leafCount); printf("\nNumber of leaves: %d\n", leafCount); return 0; } ```

阅读全文