C++非递归从文件构建二叉树的节点遍历问题

问题背景 #

输入文件内容：

0 1 3 4
0 1 4
0 2 3 3 4
0 2 3 4 

目标二叉树结构：

0
      /   \
     1     2
    / \    |
   3   4   3
   |      / \
   4     3   4
         |
         4

构建规则：每行对应一个数据序列，构建树时若序列已存在则沿其遍历，直到出现分支再创建新节点。

当前代码存在的核心问题：

• 遍历逻辑错误：仅检查当前节点的左右子节点，未沿序列路径深入遍历深层节点
• 节点更新逻辑混乱：找到匹配节点后错误覆盖currentNode为新节点，违背路径遍历逻辑
• 未按序列顺序逐元素处理路径

解决思路 #

对每一行的序列，从根节点开始逐元素沿路径处理：

1. 针对当前元素，检查当前节点的左右子节点是否存在匹配项
2. 找到匹配节点则移动到该节点，处理下一个元素
3. 未找到则创建新节点，挂到当前节点的空位置（优先左），再移动到新节点

修正后的代码示例 #

#include <sstream>
#include <string>

// 假设Node结构定义
struct Node {
    std::string data;
    Node* left;
    Node* right;
    Node(const std::string& d) : data(d), left(nullptr), right(nullptr) {}
};

class Tree {
private:
    Node* root = nullptr;
public:
    void addNewStack(const std::string& line);
};

void Tree::addNewStack(const std::string& line) {
    std::istringstream iss(line);
    std::string token;

    // 处理空树的情况
    if (root == nullptr) {
        if (!(iss >> token)) return; // 空行直接返回
        root = new Node(token);
    }

    Node* currentNode = root;
    // 逐元素处理序列
    while (iss >> token) {
        Node* matchedNode = nullptr;
        // 检查当前节点的左右子节点是否匹配
        if (currentNode->left != nullptr && currentNode->left->data == token) {
            matchedNode = currentNode->left;
        } else if (currentNode->right != nullptr && currentNode->right->data == token) {
            matchedNode = currentNode->right;
        }

        if (matchedNode != nullptr) {
            // 沿已有路径继续遍历
            currentNode = matchedNode;
        } else {
            // 创建新节点并挂载
            Node* newNode = new Node(token);
            if (currentNode->left == nullptr) {
                currentNode->left = newNode;
            } else {
                currentNode->right = newNode;
            }
            currentNode = newNode;
        }
    }
}

关键说明 #

• 严格遵循序列路径：每一行的序列被视为从根到叶子的完整路径，不会混淆不同分支的同值节点
• 非递归遍历逻辑：通过currentNode的逐次移动实现路径遍历，无需递归或复杂队列结构
• 节点挂载规则：优先挂左子节点，左子节点存在则挂右，符合目标树的结构要求

内容的提问来源于stack exchange，提问作者Mali Ika