从边列表（节点对）构建二叉树
Constructing a binary tree from a list of its edges (node pairs)
我想从一个非常不寻常的输入构造一个二叉树。输入包含：
节点总数。
根的整数标签。
所有边的列表（vertices/nodes
其他）。列表中的边是未排序的，只有一个规则
determining left/right children - 出现的边中的child
列表中的第一个总是在左边。 child/parent在顶点对中的顺序也是随机的。
我提出了一些直接的解决方案，但它们需要在所有边的列表中进行多次搜索（我基本上会找到其中带有标记根的 2 条边，并对所有子树重复此过程。 )
我认为这种直接的方法对于具有大量节点的树来说非常低效，但我想不出任何其他方法。
有没有更有效的算法来解决这个问题的想法？
这里有一个 示例，以便更好地可视化：
输入：5 个节点，根标记为 2，边列表：[(1,0),(1,2),(2,3),(1,4)]
树看起来像这样：
2
1 3
0 4
澄清给定的边列表是否声明为有向很重要。
如果以定向方式给出边（即声明任何给定的边 A-B 还包含 A 是 B 的父级的信息），则将边存储在 adjacency list while recording number of incoming edges for each vertex in an array should be sufficient. Once you go through the array for the incoming edges, the vertex with 0 incoming edges(i.e. parents) should be the root. Then you can run a DFS 中，线性时间复杂度为遍历 graph 并将其放入最适合您需要的任何数据结构中。
如果指定给定的边是无向的，则方案会有所改变。在那种情况下，您没有传入和传出边缘的概念。在那种情况下，由于没有指定数组的结构（例如 BST 等），您基本上可以将任何少于 3 条边的节点视为根节点和 运行 DFS，如上所述。 (所有的叶子节点和中间节点只有一个子节点)
一个简单的解决方案是："Link all the edges in the tree that it!"
开始准备字典。如果起点和终点不存在节点，则创建它们。由于它本质上是随机的，因此您可以先将它们的左右指针设置为 NULL。
你有规则 - “首先出现在列表中的边缘中的 child 总是在左边。”。因此，相应地创建 child。
此外，您已经知道树的根，因此您可以遍历到目前为止构建的节点。
通过这个你可以一次生成树。
希望对您有所帮助！
我想从一个非常不寻常的输入构造一个二叉树。输入包含：
节点总数。
根的整数标签。
所有边的列表（vertices/nodes 其他）。列表中的边是未排序的，只有一个规则 determining left/right children - 出现的边中的child 列表中的第一个总是在左边。 child/parent在顶点对中的顺序也是随机的。
我提出了一些直接的解决方案，但它们需要在所有边的列表中进行多次搜索（我基本上会找到其中带有标记根的 2 条边，并对所有子树重复此过程。 )
我认为这种直接的方法对于具有大量节点的树来说非常低效，但我想不出任何其他方法。
有没有更有效的算法来解决这个问题的想法？
这里有一个 示例，以便更好地可视化：
输入：5 个节点，根标记为 2，边列表：[(1,0),(1,2),(2,3),(1,4)]
树看起来像这样：
2
1 3
0 4
澄清给定的边列表是否声明为有向很重要。
如果以定向方式给出边（即声明任何给定的边 A-B 还包含 A 是 B 的父级的信息），则将边存储在 adjacency list while recording number of incoming edges for each vertex in an array should be sufficient. Once you go through the array for the incoming edges, the vertex with 0 incoming edges(i.e. parents) should be the root. Then you can run a DFS 中，线性时间复杂度为遍历 graph 并将其放入最适合您需要的任何数据结构中。
如果指定给定的边是无向的，则方案会有所改变。在那种情况下，您没有传入和传出边缘的概念。在那种情况下，由于没有指定数组的结构（例如 BST 等），您基本上可以将任何少于 3 条边的节点视为根节点和 运行 DFS，如上所述。 (所有的叶子节点和中间节点只有一个子节点)
一个简单的解决方案是："Link all the edges in the tree that it!"
开始准备字典。如果起点和终点不存在节点，则创建它们。由于它本质上是随机的，因此您可以先将它们的左右指针设置为 NULL。 你有规则 - “首先出现在列表中的边缘中的 child 总是在左边。”。因此，相应地创建 child。 此外，您已经知道树的根，因此您可以遍历到目前为止构建的节点。
通过这个你可以一次生成树。
希望对您有所帮助！