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

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语言的方法：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 定义二叉树结点结构
   
5. typedef struct TreeNode {
   
6.     int val;
   
7.     struct TreeNode* left;
   
8.     struct TreeNode* right;
   
9. } TreeNode;
   
10. 
    
11. // 栈节点
    
12. typedef struct StackNode {
    
13.     TreeNode* treeNode;
    
14.     struct StackNode* next;
    
15. } StackNode;
    
16. 
    
17. // 入栈
    
18. void push(StackNode** stack, TreeNode* treeNode) {
    
19.     StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    
20.     new_node->treeNode = treeNode;
    
21.     new_node->next = *stack;
    
22.     *stack = new_node;
    
23. }
    
24. 
    
25. // 出栈
    
26. TreeNode* pop(StackNode** stack) {
    
27.     if (*stack == NULL) {
    
28.         return NULL;
    
29.     }
    
30.     StackNode* temp = *stack;
    
31.     *stack = (*stack)->next;
    
32.     TreeNode* treeNode = temp->treeNode;
    
33.     free(temp);
    
34.     return treeNode;
    
35. }
    
36. 
    
37. // 检查栈是否为空
    
38. int isEmpty(StackNode* stack) {
    
39.     return stack == NULL;
    
40. }
    
41. 
    
42. // 新建树节点
    
43. TreeNode* newTreeNode(int value) {
    
44.     TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    
45.     node->val = value;
    
46.     node->left = node->right = NULL;
    
47.     return node;
    
48. }
    
49. 
    
50. // 构造二叉树函数，使用队列
    
51. TreeNode* buildTree(int arr[], int n) {
    
52.     if (n <= 0) return NULL;
    
53.    
    
54.     TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
    
55.     for (int i = 0; i < n; i++) {
    
56.         nodes[i] = (arr[i] != -1) ? newTreeNode(arr[i]) : NULL;
    
57.     }
    
58. 
    
59.     int j = 1;
    
60.     for (int i = 0; i < n && j < n; i++) {
    
61.         if (nodes[i] != NULL) {
    
62.             if (j < n) nodes[i]->left = nodes[j++];
    
63.             if (j < n) nodes[i]->right = nodes[j++];
    
64.         }
    
65.     }
    
66. 
    
67.     TreeNode* root = nodes[0];
    
68.     free(nodes);
    
69.     return root;
    
70. }
    
71. 
    
72. // 中序遍历非递归实现
    
73. void inorderTraversal(TreeNode* root) {
    
74.     StackNode* stack = NULL;
    
75.     TreeNode* curr = root;
    
76.     while (curr != NULL || !isEmpty(stack)) {
    
77.         // 向左遍历并入栈
    
78.         while (curr != NULL) {
    
79.             push(&stack, curr);
    
80.             curr = curr->left;
    
81.         }
    
82.         
    
83.         // 出栈并访问
    
84.         curr = pop(&stack);
    
85.         printf("%d ", curr->val);
    
86.         
    
87.         // 访问右子树
    
88.         curr = curr->right;
    
89.     }
    
90. }
    
91. 
    
92. // 主函数
    
93. int main() {
    
94.     int arr[] = {1, 2, 3, 4, 5, 6};
    
95.     int n = sizeof(arr)/sizeof(arr[0]);
    
96. 
    
97.     TreeNode* root = buildTree(arr, n);
    
98.     inorderTraversal(root);
    
99.     printf("\n");
    
100. 
     
101.     return 0;
     
102. }

复制代码

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

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

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

跳转到最佳答案楼层

FishC

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 定义二叉树结点结构
   
5. typedef struct TreeNode {
   
6.     int val;
   
7.     struct TreeNode* left;
   
8.     struct TreeNode* right;
   
9. } TreeNode;
   
10. 
    
11. // 栈节点
    
12. typedef struct StackNode {
    
13.     TreeNode* treeNode;
    
14.     struct StackNode* next;
    
15. } StackNode;
    
16. 
    
17. // 入栈
    
18. void push(StackNode** stack, TreeNode* treeNode) {
    
19.     StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    
20.     new_node->treeNode = treeNode;
    
21.     new_node->next = *stack;
    
22.     *stack = new_node;
    
23. }
    
24. 
    
25. // 出栈
    
26. TreeNode* pop(StackNode** stack) {
    
27.     if (*stack == NULL) {
    
28.         return NULL;
    
29.     }
    
30.     StackNode* temp = *stack;
    
31.     *stack = (*stack)->next;
    
32.     TreeNode* treeNode = temp->treeNode;
    
33.     free(temp);
    
34.     return treeNode;
    
35. }
    
36. 
    
37. // 检查栈是否为空
    
38. int isEmpty(StackNode* stack) {
    
39.     return stack == NULL;
    
40. }
    
41. 
    
42. // 新建树节点
    
43. TreeNode* newTreeNode(int value) {
    
44.     TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    
45.     node->val = value;
    
46.     node->left = node->right = NULL;
    
47.     return node;
    
48. }
    
49. 
    
50. // 构造二叉树函数，使用队列
    
51. TreeNode* buildTree(int arr[], int n) {
    
52.     if (n <= 0) return NULL;
    
53.    
    
54.     TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);
    
55.     for (int i = 0; i < n; i++) {
    
56.         nodes[i] = (arr[i] != -1) ? newTreeNode(arr[i]) : NULL;
    
57.     }
    
58. 
    
59.     int j = 1;
    
60.     for (int i = 0; i < n && j < n; i++) {
    
61.         if (nodes[i] != NULL) {
    
62.             if (j < n) nodes[i]->left = nodes[j++];
    
63.             if (j < n) nodes[i]->right = nodes[j++];
    
64.         }
    
65.     }
    
66. 
    
67.     TreeNode* root = nodes[0];
    
68.     free(nodes);
    
69.     return root;
    
70. }
    
71. 
    
72. // 中序遍历非递归实现
    
73. void inorderTraversal(TreeNode* root) {
    
74.     StackNode* stack = NULL;
    
75.     TreeNode* curr = root;
    
76.     while (curr != NULL || !isEmpty(stack)) {
    
77.         // 向左遍历并入栈
    
78.         while (curr != NULL) {
    
79.             push(&stack, curr);
    
80.             curr = curr->left;
    
81.         }
    
82.         
    
83.         // 出栈并访问
    
84.         curr = pop(&stack);
    
85.         printf("%d ", curr->val);
    
86.         
    
87.         // 访问右子树
    
88.         curr = curr->right;
    
89.     }
    
90. }
    
91. 
    
92. // 主函数
    
93. int main() {
    
94.     int arr[] = {1, 2, 3, 4, 5, 6};
    
95.     int n = sizeof(arr)/sizeof(arr[0]);
    
96. 
    
97.     TreeNode* root = buildTree(arr, n);
    
98.     inorderTraversal(root);
    
99.     printf("\n");
    
100. 
     
101.     return 0;
     
102. }

复制代码

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

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

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