用C语言实现二叉树中序遍历非递归算法
时间: 2024-12-19 09:23:37 浏览: 13
二叉树中序遍历
在C语言中,实现二叉树的非递归中序遍历通常需要借助栈数据结构。非递归的方法可以分为三个步骤:
1. 创建一个空栈,并将根节点压入栈中。
2. 当栈不为空时,执行循环:
a. 弹出栈顶元素,访问该元素(即当前节点)。
b. 如果当前节点有左子节点,将左子节点压入栈中。
c. 如果当前节点有右子节点,因为我们要按照"左-根-右"的顺序访问,跳过右子节点直接处理下一个节点(即检查下一个栈顶元素)。
3. 当栈为空且所有节点都已访问完,遍历结束。
以下是C语言的一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 非递归中序遍历函数
void inorderTraversal(TreeNode* root) {
if (root == NULL) return; // 如果根节点为空,直接返回
Stack<TreeNode*> stack; // 使用栈来辅助遍历
TreeNode* curr = root; // 初始化当前节点
while (curr != NULL || !stack.isEmpty()) { // 循环直到栈为空且当前节点也为空
while (curr != NULL) {
stack.push(curr); // 将当前节点压栈
curr = curr->left; // 转向左子节点
}
curr = stack.pop(); // 弹出栈顶节点并访问
printf("%d ", curr->val); // 打印节点值
curr = curr->right; // 移动到右子节点
}
}
int main() {
// 示例二叉树
TreeNode* root = malloc(sizeof(TreeNode));
root->val = 1;
root->left = malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = malloc(sizeof(TreeNode));
root->left->right->val = 5;
inorderTraversal(root);
return 0;
}
```
运行此程序会打印出:`4 2 5 1 3`,这是二叉树 `1 - 2(4 5) - 3` 的中序遍历结果。
阅读全文