[已解决]非递归的中序遍历

yangzhixiaohuli

非递归的中序遍历
【问题描述】

给定二叉树，返回它的中序遍历。

要求：使用栈实现，不可使用递归。

【输入形式】

一行，包含用空格分开的n个元素，每个元素为整数或者None（None表示空结点），依次表示按自顶向下层次遍历的二叉树结点。空结点对应的“孩子”（实际上不存在）不再用None表示。

【输出形式】

一行，二叉树的中序遍历，每个值间用空格隔开。

【样例输入】

1 2 3 4 5 6
【样例输出】

4 2 5 1 6 3
【问题描述】

给定二叉树，返回它的中序遍历。

要求：使用栈实现，不可使用递归。

【输入形式】

一行，包含用空格分开的n个元素，每个元素为整数或者None（None表示空结点），依次表示按自顶向下层次遍历的二叉树结点。空结点对应的“孩子”（实际上不存在）不再用None表示。

【输出形式】

一行，二叉树的中序遍历，每个值间用空格隔开。

【样例输入】

1 2 3 4 5 6
【样例输出】

4 2 5 1 6 3

这题用C或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-29 16:45:29

给定的二叉树使用层次遍历的顺序输入，你需要构造二叉树并实现非递归的中序遍历。以下是使用C语言的方法：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点结构
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈节点
typedef struct StackNode {
    TreeNode* treeNode;
    struct StackNode* next;
} StackNode;

// 入栈
void push(StackNode** stack, TreeNode* treeNode) {
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->treeNode = treeNode;
    new_node->next = *stack;
    *stack = new_node;
}

// 出栈
TreeNode* pop(StackNode** stack) {
    if (*stack == NULL) {
        return NULL;
    }
    StackNode* temp = *stack;
    *stack = (*stack)->next;
    TreeNode* treeNode = temp->treeNode;
    free(temp);
    return treeNode;
}

// 检查栈是否为空
int isEmpty(StackNode* stack) {
    return stack == NULL;
}

// 新建树节点
TreeNode* newTreeNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = value;
    node->left = node->right = NULL;
    return node;
}

// 构造二叉树函数，使用队列
TreeNode* buildTree(int arr[], int n) {
    if (n <= 0) return NULL;
    
    TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
    for (int i = 0; i < n; i++) {
        nodes[i] = (arr[i] != -1) ? newTreeNode(arr[i]) : NULL;
    }

    int j = 1;
    for (int i = 0; i < n && j < n; i++) {
        if (nodes[i] != NULL) {
            if (j < n) nodes[i]->left = nodes[j++];
            if (j < n) nodes[i]->right = nodes[j++];
        }
    }

    TreeNode* root = nodes[0];
    free(nodes);
    return root;
}

// 中序遍历非递归实现
void inorderTraversal(TreeNode* root) {
    StackNode* stack = NULL;
    TreeNode* curr = root;
    while (curr != NULL || !isEmpty(stack)) {
        // 向左遍历并入栈
        while (curr != NULL) {
            push(&stack, curr);
            curr = curr->left;
        }
        
        // 出栈并访问
        curr = pop(&stack);
        printf("%d ", curr->val);
        
        // 访问右子树
        curr = curr->right;
    }
}

// 主函数
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    TreeNode* root = buildTree(arr, n);
    inorderTraversal(root);
    printf("\n");

    return 0;
}

注意：
- 树节点使用`-1`表示`None`，表示输入时不存在的节点。
- 实现了一个简单的堆栈来协助中序遍历。
- `buildTree`函数构建二叉树时，假设输入按层次顺序。
- 中序遍历依次访问左子树、根节点、右子树的顺序。

以上代码中使用了简单的堆栈结构实现对树的非递归中序遍历。请确保输入按照树的层次顺序，否则构建的二叉树可能不符合预期。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

给定的二叉树使用层次遍历的顺序输入，你需要构造二叉树并实现非递归的中序遍历。以下是使用C语言的方法：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点结构
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈节点
typedef struct StackNode {
    TreeNode* treeNode;
    struct StackNode* next;
} StackNode;

// 入栈
void push(StackNode** stack, TreeNode* treeNode) {
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->treeNode = treeNode;
    new_node->next = *stack;
    *stack = new_node;
}

// 出栈
TreeNode* pop(StackNode** stack) {
    if (*stack == NULL) {
        return NULL;
    }
    StackNode* temp = *stack;
    *stack = (*stack)->next;
    TreeNode* treeNode = temp->treeNode;
    free(temp);
    return treeNode;
}

// 检查栈是否为空
int isEmpty(StackNode* stack) {
    return stack == NULL;
}

// 新建树节点
TreeNode* newTreeNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = value;
    node->left = node->right = NULL;
    return node;
}

// 构造二叉树函数，使用队列
TreeNode* buildTree(int arr[], int n) {
    if (n <= 0) return NULL;
    
    TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
    for (int i = 0; i < n; i++) {
        nodes[i] = (arr[i] != -1) ? newTreeNode(arr[i]) : NULL;
    }

    int j = 1;
    for (int i = 0; i < n && j < n; i++) {
        if (nodes[i] != NULL) {
            if (j < n) nodes[i]->left = nodes[j++];
            if (j < n) nodes[i]->right = nodes[j++];
        }
    }

    TreeNode* root = nodes[0];
    free(nodes);
    return root;
}

// 中序遍历非递归实现
void inorderTraversal(TreeNode* root) {
    StackNode* stack = NULL;
    TreeNode* curr = root;
    while (curr != NULL || !isEmpty(stack)) {
        // 向左遍历并入栈
        while (curr != NULL) {
            push(&stack, curr);
            curr = curr->left;
        }
        
        // 出栈并访问
        curr = pop(&stack);
        printf("%d ", curr->val);
        
        // 访问右子树
        curr = curr->right;
    }
}

// 主函数
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    TreeNode* root = buildTree(arr, n);
    inorderTraversal(root);
    printf("\n");

    return 0;
}

注意：
- 树节点使用`-1`表示`None`，表示输入时不存在的节点。
- 实现了一个简单的堆栈来协助中序遍历。
- `buildTree`函数构建二叉树时，假设输入按层次顺序。
- 中序遍历依次访问左子树、根节点、右子树的顺序。

以上代码中使用了简单的堆栈结构实现对树的非递归中序遍历。请确保输入按照树的层次顺序，否则构建的二叉树可能不符合预期。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。