【数据结构】假设二叉树采用二叉链表存储，编写一棵二又树中序遍历的非递归算法。

编程题：

假设二叉树采用二叉链表存储，编写一棵二又树中序遍历的非递归算法。

在这里插入图片描述

分析：
算法描述：
非递归中序遍历二叉树的算法使用栈来辅助实现。首先，从根节点开始，沿着左子树不断向下，
将每个节点压入栈中。当到达最左端节点后，开始出栈并访问节点，接着转向右子树，重复这
一过程，直到栈为空且当前节点为 NULL。这种方法确保按左-根-右的顺序访问每个节点。

#include <stdio.h>
#include <stdlib.h>
/*
七、（16 分)假设二叉树采用二叉链表存储，编写一棵二又树中序遍历的非递归算法。
算法描述：
非递归中序遍历二叉树的算法使用栈来辅助实现。首先，从根节点开始，沿着左子树不断向下，
将每个节点压入栈中。当到达最左端节点后，开始出栈并访问节点，接着转向右子树，重复这
一过程，直到栈为空且当前节点为 NULL。这种方法确保按左-根-右的顺序访问每个节点。
*/#if 0
typedef struct TreeNode {int data;                  // 节点数据struct TreeNode* left;    // 左子树指针struct TreeNode* right;   // 右子树指针
} TreeNode;//非递归中序遍历算法
void inorderTraversal(TreeNode* root) {TreeNode** stack = (TreeNode**)malloc(100 * sizeof(TreeNode*)); // 动态分配栈int top = -1;         // 栈顶指针TreeNode* current = root;while (current != NULL || top != -1) {// 将所有左子树节点压入栈中while (current != NULL) {stack[++top] = current; // 压入栈current = current->left; // 移动到左子节点}// 处理栈顶节点current = stack[top--]; // 弹出栈顶节点printf("%d ", current->data); // 访问节点// 处理右子树current = current->right; // 移动到右子节点}free(stack); // 释放栈内存
}int main() {// 构建一个简单的二叉树TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->data = 1;root->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->data = 2;root->right = (TreeNode*)malloc(sizeof(TreeNode));root->right->data = 3;root->left->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->left->data = 4;root->left->right = (TreeNode*)malloc(sizeof(TreeNode));root->left->right->data = 5;root->left->left->left = NULL; // 确保左子树指针为NULLroot->left->left->right = NULL;root->left->right->left = NULL;root->left->right->right = NULL;root->right->left = NULL;root->right->right = NULL;// 中序遍历printf("中序遍历结果: ");inorderTraversal(root); // 输出: 4 2 5 1 3printf("\n");// 释放内存free(root->left->right);free(root->left->left);free(root->left);free(root->right);free(root);return 0;
}
#endif

在这里插入图片描述

//非递归中序遍历算法
void inorderTraversal(TreeNode* root) {TreeNode** stack = (TreeNode**)malloc(100 * sizeof(TreeNode*)); // 动态分配栈int top = -1;         // 栈顶指针TreeNode* current = root;while (current != NULL || top != -1) {// 将所有左子树节点压入栈中while (current != NULL) {stack[++top] = current; // 压入栈current = current->left; // 移动到左子节点}// 处理栈顶节点current = stack[top--]; // 弹出栈顶节点printf("%d ", current->data); // 访问节点// 处理右子树current = current->right; // 移动到右子节点}free(stack); // 释放栈内存
}