从文件创建二叉树，无需递归C++

Question

首先，我想道歉，因为我不知道如何恰当地表达标题。这是我遇到的问题。 我在从文件创建树时遇到问题。 该文件如下所示：

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

用文字来解释，在文件的每一行中，我都会得到一个新的数据堆栈，我应该创建一棵树，但如果序列存在，我应该遵循它，直到其中出现中断。

在创建树时，我使用此方法来检查是否存在已经存在的序列：

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

Node* currentNode = nullptr;

while (stack >> token) {
    Node* newNode = new Node(token);

    if (root == nullptr) {
        root = newNode;
    }
    else {
        // Checking for existing node.
        Node* existingNode = nullptr;
        currentNode = root;

        while (existingNode == nullptr && currentNode != nullptr) {
            if (currentNode->left != nullptr && current->left->data == token) {
                existingNode = currentNode->left;
            }
            else if (currentNode->right != nullptr && current->right->data == token) {
                existingNode = currentNode->right;
            }
            // ****
        }
        // If there is an existingNode move to it, otherwise make a new node.
        if (existingNode != nullptr) {
            currentNode = existingNode;
            currentNode = newNode;
        }
    else {
                currentNode = newNode;
            }
        }
    }
}

我尝试制作一个优先级队列，然后使用先序遍历制作一棵树，但这似乎更复杂。

在带星号的注释所在的 while 循环内，我不知道如何搜索整个循环。我需要找到一种方法来更新 currentNode，以便遍历整棵树。我尝试使用 currentNode = currentNode->left，但这仅检查树的一侧。还尝试制作 2 个 while 循环，一个检查左侧，一个检查右侧，但这也不起作用。有什么建议吗？

Answer 1

你的树上只有 1 个根。因此，您应该在 while 循环之前

而不是在循环内部处理它：检查该行的第一个标记以查看它是否与根匹配（如果不存在，则保留创建根的代码），然后初始化 

currentNode

 与它一起。

根据您的问题，其余部分应该可以轻松地用于二叉树（不是二叉

search

树）；我们将在每个级别的 left 之前填写

right

：

while (stack >> token) {
    if (!currentNode->left)
        currentNode = currentNode->left = new Node(token);
    else if (currentNode->left->data == token)
        currentNode = currentNode->left;
    else if (!currentNode->right)
        currentNode = currentNode->right = new Node(token);
    else if (currentNode->right->data == token)
        currentNode = currentNode->right;
    else
        throw "Path is incompatible with tree";
}