解析树知道所有父节点和叶节点的祖先

如果知道所有节点的直接父节点，则构建树就相当直接了。但是如果你有关于叶节点（包括祖父母，祖父母等）的所有父母的信息而不知道它是否是直接父母或者不是父母，解析树知道所有父节点和叶节点的祖先

例如，考虑下面的树：

   A -----> B ------> C -----> G 

         | 

         D ------> E 

         | 

         F

可用来描述这种树的信息是以下CSV文件：

子女，父母

E，d

Ë ，B

E，A

楼d

F，B

G，C

G，B

G，A

F，A

您能给一些建议一般algortihm解决这个问题？

2010-11-16 kms333

parents(F) = {A,B,D} 
parents(E) = {A,B,D} 
parents(G) = {A,B,C}

这是不可能从这个数据集重新的树，因为显然我们不能从这些数据哪个节点是根看，是A还是B？

2010-11-16 15:22:53

安德烈亚斯是对的 - 我以为你有所有节点的数据，而不仅仅是叶子。 – 2010-11-16 15:26:05

如果A有其他孩子，只要孩子的顺序无关紧要，你就可以重建树，因为你可以分辨出A和B之间的区别。实际上，他们“看起来是一样的”。 – 2010-11-16 15:32:32

Thansk很多！所以我可以在以下情况下计算出树：1）每个节点都有两个节点，或者2）如果节点只有一个孩子，我不关心它们的顺序。对？ – kms333 2010-11-16 15:42:29

回答