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

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++实现非递归中序遍历二叉树的示例代码，使用栈来辅助实现遍历。首先，将输入的数据构造成二叉树，然后进行中序遍历。

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 创建二叉树
TreeNode* createTree(vector<string>& nodes) {
    if (nodes.empty() || nodes[0] == "None") return nullptr;
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    vector<TreeNode*> nodeQueue = {root};
    int index = 1;
    // 通过字符串数组构建二叉树
    for (TreeNode* node : nodeQueue) {
        if (index < nodes.size() && nodes[index] != "None") {
            node->left = new TreeNode(stoi(nodes[index]));
            nodeQueue.push_back(node->left);
        }
        index++;
        if (index < nodes.size() && nodes[index] != "None") {
            node->right = new TreeNode(stoi(nodes[index]));
            nodeQueue.push_back(node->right);
        }
        index++;
    }
    return root;
}

// 二叉树的非递归中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> s;
    TreeNode* currentNode = root;
    
    while (currentNode != nullptr || !s.empty()) {
        // 找到最左边的节点
        while (currentNode != nullptr) {
            s.push(currentNode);
            currentNode = currentNode->left;
        }
        
        // 访问栈顶节点
        currentNode = s.top();
        s.pop();
        result.push_back(currentNode->val);
        
        // 访问右子树
        currentNode = currentNode->right;
    }
    
    return result;
}

int main() {
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> nodes;
    string node;
    while (iss >> node) {
        nodes.push_back(node);
    }
    
    TreeNode* root = createTree(nodes);
    vector<int> result = inorderTraversal(root);
    
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

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

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

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

跳转到最佳答案楼层

FishC

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

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 创建二叉树
TreeNode* createTree(vector<string>& nodes) {
    if (nodes.empty() || nodes[0] == "None") return nullptr;
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    vector<TreeNode*> nodeQueue = {root};
    int index = 1;
    // 通过字符串数组构建二叉树
    for (TreeNode* node : nodeQueue) {
        if (index < nodes.size() && nodes[index] != "None") {
            node->left = new TreeNode(stoi(nodes[index]));
            nodeQueue.push_back(node->left);
        }
        index++;
        if (index < nodes.size() && nodes[index] != "None") {
            node->right = new TreeNode(stoi(nodes[index]));
            nodeQueue.push_back(node->right);
        }
        index++;
    }
    return root;
}

// 二叉树的非递归中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> s;
    TreeNode* currentNode = root;
    
    while (currentNode != nullptr || !s.empty()) {
        // 找到最左边的节点
        while (currentNode != nullptr) {
            s.push(currentNode);
            currentNode = currentNode->left;
        }
        
        // 访问栈顶节点
        currentNode = s.top();
        s.pop();
        result.push_back(currentNode->val);
        
        // 访问右子树
        currentNode = currentNode->right;
    }
    
    return result;
}

int main() {
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> nodes;
    string node;
    while (iss >> node) {
        nodes.push_back(node);
    }
    
    TreeNode* root = createTree(nodes);
    vector<int> result = inorderTraversal(root);
    
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

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

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

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