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

编程题：

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

分析：
算法描述：
非递归中序遍历二叉树的算法使用栈来辅助实现。首先，从根节点开始，沿着左子树不断向下，
将每个节点压入栈中。当到达最左端节点后，开始出栈并访问节点，接着转向右子树，重复这
一过程，直到栈为空且当前节点为 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; // 确保左子树指针为NULL
    root->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 3
    printf("\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); // 释放栈内存
}

解法不一，欢迎评论区交流。

原文地址：https://blog.csdn.net/weixin_51086862/article/details/142387878

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！