如何创建一个树，找到正确的节点来添加子节点？

什么是最好的方式来建立一个树的输入给出格式(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部分），因为节点可以使用的子节点数量有没有固定。

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

来源

2013-10-25 StarShire

问题可能更适合程序员.stackexchange.com。另请参阅http://meta.stackexchange.com/questions/82988/choosing-between-stack-overflow-and-programmers-stack-exchange – grasbueschel

你能否防止类似情况发生？ 1 2，2 1;基本上是父 - >子，孩子 - >父母的循环。 – Justin

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

当您收到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-25 07:05:31

嗯...我想过，但我现在有另一个问题：在我建立树后，叶节点（他们没有任何孩子的节点）将有一个给定的输入值（一个不同于值' （A，b）'）。我需要以某种方式递归计算每个节点的值，其中父节点等于子节点的所有值的总和。这是否适用于您提供的方法？ – StarShire

它通常足以存储子节点的链接列表（或数组）（尽管取决于树的类型，其他表示可能更有效）。

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

当您在寻找a时，您只需在地图或阵列中查找它即可。

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

我需要递归遍历树倒

这将涉及简单breadth-first search或depth-first search。

来源

2013-10-25 07:46:17 Dukeling

如何创建一个树，找到正确的节点来添加子节点？

回答

相关问题