鱼C论坛

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

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

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

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

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

x
【问题描述】

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

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

【输入形式】

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

【输出形式】

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

【样例输入】

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

4 2 5 1 6 3

这题用C语言或者C++怎么实现
最佳答案
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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-12-7 04:10

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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