c++ - 如何从边缘制作二叉树？

Question

我从 from 的输入中获取二叉树的所有边

   parentId childId
   e.g. 0 3 // means from node 0 to node 3
   // 0 does not mean root of the tree.

我如何从中构造树？

Answer 1

一种方法是分两次执行：

1. 组装树中的所有链接。
2. 找到树的根。

要组装所有链接，您可以首先构建一个以每个节点的 ID 为键的哈希表（如果您知道 ID 都在 0 ... N 范围内，则可以构建一个适当大小的巨型数组以供选择） N)。每当您从文件中读取一行时，您都可以执行以下操作：

1. 如果节点不存在由起点和终点指定的 ID，则创建这些节点并最初将它们的左右指针设置为 NULL。
2. 将第二个节点添加为第一个节点的子节点。（我假设这不是二叉搜索树，所以孩子的顺序无关紧要。如果这是二叉搜索树，那么您可以根据找到的内容设置适当的孩子指针）。

要找到树的根，您可以创建一组节点作为根节点的候选节点，最初是树中的每个节点。然后，您可以遍历到目前为止已构建的节点。每次你发现一个节点 v 是另一个节点 u 的子节点时，你可以从候选根集合中删除节点 v（因为它是一个子节点）。完成后，您将得到所有可能的根集。如果边列表确实定义了一棵二叉树，那么这将只是一个节点。如果它定义了一个二叉树的森林，这将为您提供森林中所有树的根。

总的来说，这需要 O(n) 时间，其中 n 是边数（也是树中的节点数，因为二叉树中的边数是节点数减一）。

如果您愿意，可以将这两个通道合并为一个通道；为了便于展示，我只是分别描述了它们。

希望这可以帮助！

Answer 2

首先你建立一个节点ID的地图，连接节点的列表，
然后遍历地图并创建从你的信息到地图中的链接

如果是二叉树，则文件中缺少信息，格式中应该有

parent、leftChild、rightChild 或
or 和 left 和 right 总是按相同的顺序（左在前），每个节点两行，第二行在下一行。