0

构建一棵树的最佳方法是什么，其中输入给出格式(a,b)，a是父节点b还是子节点？（节点 1 是根）例如：

1 2 //adds node #2 as the children of #1 (the root)
1 3 //adds node #3 as the second children of the root
2 4 //adds node #4 as the children of node #2
etc...

如果它像二叉树，我了解如何制作这种树（因为对于给定的父节点，左孩子是较小的值，而右孩子是较大的）。但是，对于我的树，父节点可以拥有的子节点数量并不固定。我怎样才能有效地创建它？我无法理解算法如何迭代并找到正确的节点（a输入的一部分），以便它可以添加另一个节点作为子节点（b输入的一部分），因为节点可以拥有的子节点数量是不固定。

编辑：我想补充的另一件事：每个叶节点（没有子节点的节点）将被分配一些值。我需要递归（或其他方法）遍历树，以便计算每个节点的值：父节点值是其所有子节点值的总和。

4

2 回答 2

0

在每个节点中存储右孩子和兄弟地址。

当您收到时a,b，如果节点a没有右孩子插入b为右孩子，如果有右孩子跟随右孩子的兄弟姐妹找到最后一个孩子并b作为最后一个节点的兄弟姐妹插入。

遍历树：

我认为这个算法可以深度优先遍历树：

traverse(Node) 
 visit (Node) // pre order 
 if (Node.RightChild != Null)
  n = Node.RightChild
  while(n.LeftSibling != Null)
   traverse ( n.LeftSibling )
   n = n.LeftSibling
  end
 end
end
于 2013-10-25T07:05:31.737 回答
0

通常将子节点存储为链表（或数组）就足够了（尽管根据树的类型，其他表示可能更有效）。

通常你会有一个地图或节点数组。

当您在寻找 时a，您只需在地图或数组中进行查找即可。

然后，您只需添加b到子列表中。

我需要递归遍历树

这将涉及简单的广度优先搜索或深度优先搜索。

于 2013-10-25T07:46:17.203 回答