C语言二叉树中序非递归遍历

### C语言实现二叉树中序非递归遍历方法 在C语言中，可以通过栈来模拟递归过程从而实现二叉树的中序非递归遍历。以下是具体的实现方式： #### 使用栈结构辅助遍历 为了实现非递归版本的中序遍历，可以借助显式的栈数据结构存储节点指针。具体逻辑如下： 1. 初始化一个指向根节点的指针 `current` 和一个用于存储节点地址的栈。 2. 当前节点不为空或者栈不为空时进入循环： - 如果当前节点存在，则将其压入栈，并继续向其左子树移动。 - 若当前节点不存在（即到达最左侧叶子），则弹出栈顶元素并访问它，随后转向该节点的右子树。 这种方法能够按照“左-根-右”的顺序依次访问所有节点[^1]。 下面是完整的代码示例： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构体 typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建新节点函数 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } // 栈定义及其操作 #define MAX_STACK_SIZE 100 struct Stack { TreeNode* items[MAX_STACK_SIZE]; int top; }; void initStack(struct Stack* stack) { stack->top = -1; } int isEmpty(struct Stack* stack) { return stack->top == -1; } int isFull(struct Stack* stack) { return stack->top >= MAX_STACK_SIZE - 1; } void push(struct Stack* stack, TreeNode* item) { if (!isFull(stack)) { stack->items[++stack->top] = item; } else { printf("Error: Stack Overflow\n"); } } TreeNode* pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->items[stack->top--]; else { printf("Error: Stack Underflow\n"); return NULL; } } // 非递归中序遍历函数 void inorderTraversalNonRecursive(TreeNode* root) { struct Stack s; initStack(&s); TreeNode* current = root; while (current != NULL || !isEmpty(&s)) { // 将左子树全部压入栈 while (current != NULL) { push(&s, current); current = current->left; } // 弹出栈顶元素并打印 current = pop(&s); printf("%d ", current->data); // 访问节点 // 转到右子树 current = current->right; } } // 测试程序 int main() { // 构建测试用的二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7); // 执行非递归中序遍历 printf("Inorder Traversal (Non-recursive): "); inorderTraversalNonRecursive(root); printf("\n"); return 0; } ``` 此代码实现了基于栈的二叉树中序非递归遍历功能[^1]。通过创建自定义栈以及一系列基本操作，成功完成了对任意形状二叉树按需输出的任务。