鱼C论坛

 找回密码
 立即注册
查看: 59|回复: 1

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

[复制链接]
发表于 2024-11-29 16:44:20 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

要求:使用栈实现,不可使用递归。

【输入形式】

一行,包含用空格分开的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++怎么做
最佳答案
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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-7 03:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表