c++ - 如何逐步构建具有依赖关系的非二叉树

Question

简短描述
我需要建立一个非二进制的树（语言现在不重要，但最好是C++）。
节点的数据从文件中读取，并以增量方式插入到树中。
最麻烦的部分是如何处理那些还没有父节点的节点，以满足插入节点的依赖性。
详细说明
粗略的轮廓
分配很简单：在非二叉树中表示一堆任务和子任务。
如果不是因为一个很小的条件，这个分配将非常容易理解和实现：任务列表必须增量生成，树中的节点也必须增量生成。
脚本
任务是异步生成的，一旦接收到某个任务的数据，就必须将其添加到树中。
这是通过读取csv文件来“模拟”的，该文件的每一行都有特定的任务和一些数据，其中最重要的是pid和ppid属性。
读取并解析行之后，将创建一个任务并将其插入树中。
树应按照以下两个简单规则自动解析依赖项：
只在满足依赖关系时（即以前插入父节点时）显示节点，但记住（现在是孤立的）节点。
每当添加任务（节点）时，请检查它是否是上述任意孤立任务之一的父节点，并在执行此操作时协调规则1是否未被违反的节点。
请忽略这一方案背后的错误逻辑：通常，没有任何子任务（至少在整体内核设计中）是不可能存在任何子任务的。
虽然任务列表确实包含建模树所需的parenttasks，但是当parentnode数据被读取并插入到树中时，它是未知的。
期望结果
下面是一个显示“原始数据”的图，这是一个（未排序的）任务列表，在将一个又一个任务添加到列表中时以增量方式创建。
树表示到目前为止插入的任务子集：

请记住，在插入带有pids 1、2和3的任务之前，树是完全“裸”的，因为其他节点都依赖于它们。
我到目前为止所做的
我已经编写了一个QT-C++代码，包含三个粗糙的组件：
包含根节点的任务树（没有任何任务数据的节点）
TaskNode有一个字段来保存任务数据，QList 简单地说，QList 是引用子节点的TaskNodes向量
任务具有相关属性（如pid和ppid）
如果帕伦特节点已经存在，插入任务节点是没有问题的。
这只适用于一个完美的世界，在这个世界中，任务按照各自的依赖关系进行排序，并且要添加的任务数量是确定的。
不过，我不必告诉您这样的场景是不太可能的，因此树的创建必须记住任何孤立节点（这是一个还没有父节点的节点，duh）。
我已经用不同的方法解决了这个“记忆”的问题，但都失败了，因为我无法将我的头脑集中在它背后的算法上。
我最有希望的两个想法是：
将每个孤立节点插入向量。插入parentnode时，检查它在孤立向量中是否有子节点并进行协调为新创建的子树递归执行此操作，以匹配所有可能的子树。
将ppid分配给树的rootnode，最上面的为0。出现孤立节点时，创建新的任务树，将孤立节点的PPID分配给新创建的树，并将孤立节点添加到该树中。
这就产生了子树，如果几个孤儿匹配其中一棵树，子树就可以脱离复杂的自我在每个插入的节点之后，尝试将子树与根树协调。
不幸的是，我不得不放弃继续这两个概念，因为几个自发的sigsegv和其他问题发生的递归等。
所以最后，我在这里试图找到一种方法来真正做到这一点，而不是通过假设和其他骗局来降低问题的复杂性。
你们知道我可以用哪种算法来解决这个问题，或者这是哪一类问题吗？

Answer 1

方法2是正确的。您缺少的部分是，您需要一个名为unordered_map的node_needed节点，它将尚未看到的父节点映射到等待它的子树的vector节点。对于已经看到的节点，您需要一个类似的映射node_seen到关联树。
然后，当您看到一个节点时，执行以下操作：

Create TaskTree with only this node.
Add this TaskTree to the node_seen map

If this node's ID is in the parent_needed map:
    Add each tree in the parent_needed map to this tree
    Remove this node's ID from the parent_needed map

If this node has no parent:
    Add this node's tree to the root tree
Else if this node's parent ID is in the node_seen map:
    Add this node's tree to the parent tree
Else if this node's parent_ID is in the parent_needed map:
    Append this node's tree to the parent_needed vector
Else:
    Create a vector containing this node's tree
    Add a mapping from this node's parent ID to that vector in the parent_needed map

假设没有虫子（哈哈！虫子是生命的一部分……，这应该管用。