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

yangzhixiaohuli

【问题描述】

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

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

【输入形式】

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

【输出形式】

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

【样例输入】

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

4 2 5 1 6 3

这题用C语言或者C++怎么实现

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-29 17:13:44

下面是C++实现非递归中序遍历二叉树的示例代码，使用栈来辅助实现遍历。首先，将输入的数据构造成二叉树，然后进行中序遍历。

1. #include <iostream>
   
2. #include <sstream>
   
3. #include <vector>
   
4. #include <stack>
   
5. #include <string>
   
6. 
   
7. using namespace std;
   
8. 
   
9. // 定义二叉树节点结构体
   
10. struct TreeNode {
    
11.     int val;
    
12.     TreeNode *left;
    
13.     TreeNode *right;
    
14.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    
15. };
    
16. 
    
17. // 创建二叉树
    
18. TreeNode* createTree(vector<string>& nodes) {
    
19.     if (nodes.empty() || nodes[0] == "None") return nullptr;
    
20.     TreeNode* root = new TreeNode(stoi(nodes[0]));
    
21.     vector<TreeNode*> nodeQueue = {root};
    
22.     int index = 1;
    
23.     // 通过字符串数组构建二叉树
    
24.     for (TreeNode* node : nodeQueue) {
    
25.         if (index < nodes.size() && nodes[index] != "None") {
    
26.             node->left = new TreeNode(stoi(nodes[index]));
    
27.             nodeQueue.push_back(node->left);
    
28.         }
    
29.         index++;
    
30.         if (index < nodes.size() && nodes[index] != "None") {
    
31.             node->right = new TreeNode(stoi(nodes[index]));
    
32.             nodeQueue.push_back(node->right);
    
33.         }
    
34.         index++;
    
35.     }
    
36.     return root;
    
37. }
    
38. 
    
39. // 二叉树的非递归中序遍历
    
40. vector<int> inorderTraversal(TreeNode* root) {
    
41.     vector<int> result;
    
42.     stack<TreeNode*> s;
    
43.     TreeNode* currentNode = root;
    
44.    
    
45.     while (currentNode != nullptr || !s.empty()) {
    
46.         // 找到最左边的节点
    
47.         while (currentNode != nullptr) {
    
48.             s.push(currentNode);
    
49.             currentNode = currentNode->left;
    
50.         }
    
51.         
    
52.         // 访问栈顶节点
    
53.         currentNode = s.top();
    
54.         s.pop();
    
55.         result.push_back(currentNode->val);
    
56.         
    
57.         // 访问右子树
    
58.         currentNode = currentNode->right;
    
59.     }
    
60.    
    
61.     return result;
    
62. }
    
63. 
    
64. int main() {
    
65.     string input;
    
66.     getline(cin, input);
    
67.     istringstream iss(input);
    
68.     vector<string> nodes;
    
69.     string node;
    
70.     while (iss >> node) {
    
71.         nodes.push_back(node);
    
72.     }
    
73.    
    
74.     TreeNode* root = createTree(nodes);
    
75.     vector<int> result = inorderTraversal(root);
    
76.    
    
77.     for (size_t i = 0; i < result.size(); ++i) {
    
78.         if (i > 0) cout << " ";
    
79.         cout << result[i];
    
80.     }
    
81.     cout << endl;
    
82.    
    
83.     return 0;
    
84. }

复制代码

**代码说明：**
- 首先定义了一个二叉树的节点结构。
- 使用`createTree`函数根据输入创建二叉树。
- 使用`inorderTraversal`函数进行非递归中序遍历。
- 主函数中读取输入，调用以上函数，最后输出结果。

你可以根据这个思路用C实现。C++标准库中提供的`stack`类是实现非递归遍历的关键部分。

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

跳转到最佳答案楼层

FishC

下面是C++实现非递归中序遍历二叉树的示例代码，使用栈来辅助实现遍历。首先，将输入的数据构造成二叉树，然后进行中序遍历。

1. #include <iostream>
   
2. #include <sstream>
   
3. #include <vector>
   
4. #include <stack>
   
5. #include <string>
   
6. 
   
7. using namespace std;
   
8. 
   
9. // 定义二叉树节点结构体
   
10. struct TreeNode {
    
11.     int val;
    
12.     TreeNode *left;
    
13.     TreeNode *right;
    
14.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    
15. };
    
16. 
    
17. // 创建二叉树
    
18. TreeNode* createTree(vector<string>& nodes) {
    
19.     if (nodes.empty() || nodes[0] == "None") return nullptr;
    
20.     TreeNode* root = new TreeNode(stoi(nodes[0]));
    
21.     vector<TreeNode*> nodeQueue = {root};
    
22.     int index = 1;
    
23.     // 通过字符串数组构建二叉树
    
24.     for (TreeNode* node : nodeQueue) {
    
25.         if (index < nodes.size() && nodes[index] != "None") {
    
26.             node->left = new TreeNode(stoi(nodes[index]));
    
27.             nodeQueue.push_back(node->left);
    
28.         }
    
29.         index++;
    
30.         if (index < nodes.size() && nodes[index] != "None") {
    
31.             node->right = new TreeNode(stoi(nodes[index]));
    
32.             nodeQueue.push_back(node->right);
    
33.         }
    
34.         index++;
    
35.     }
    
36.     return root;
    
37. }
    
38. 
    
39. // 二叉树的非递归中序遍历
    
40. vector<int> inorderTraversal(TreeNode* root) {
    
41.     vector<int> result;
    
42.     stack<TreeNode*> s;
    
43.     TreeNode* currentNode = root;
    
44.    
    
45.     while (currentNode != nullptr || !s.empty()) {
    
46.         // 找到最左边的节点
    
47.         while (currentNode != nullptr) {
    
48.             s.push(currentNode);
    
49.             currentNode = currentNode->left;
    
50.         }
    
51.         
    
52.         // 访问栈顶节点
    
53.         currentNode = s.top();
    
54.         s.pop();
    
55.         result.push_back(currentNode->val);
    
56.         
    
57.         // 访问右子树
    
58.         currentNode = currentNode->right;
    
59.     }
    
60.    
    
61.     return result;
    
62. }
    
63. 
    
64. int main() {
    
65.     string input;
    
66.     getline(cin, input);
    
67.     istringstream iss(input);
    
68.     vector<string> nodes;
    
69.     string node;
    
70.     while (iss >> node) {
    
71.         nodes.push_back(node);
    
72.     }
    
73.    
    
74.     TreeNode* root = createTree(nodes);
    
75.     vector<int> result = inorderTraversal(root);
    
76.    
    
77.     for (size_t i = 0; i < result.size(); ++i) {
    
78.         if (i > 0) cout << " ";
    
79.         cout << result[i];
    
80.     }
    
81.     cout << endl;
    
82.    
    
83.     return 0;
    
84. }

复制代码

**代码说明：**
- 首先定义了一个二叉树的节点结构。
- 使用`createTree`函数根据输入创建二叉树。
- 使用`inorderTraversal`函数进行非递归中序遍历。
- 主函数中读取输入，调用以上函数，最后输出结果。

你可以根据这个思路用C实现。C++标准库中提供的`stack`类是实现非递归遍历的关键部分。

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