如何创建树，找到添加子节点的正确节点？-Java 学习之路

构建树的最佳方法是什么，输入格式为 (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 部分），因为节点的子节点数量可以有没有固定 .

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

2 回答

0

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

通常，您有一个 Map 或节点数组 .

当你在寻找 a 时，你只需要在 Map 或数组中查找它 .

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

我需要以递归方式遍历树

这将涉及一个简单的breadth-first search或depth-first search .

回复于 2024-04-19T07:06:37+08:00
0
存储每个节点中的右子节点和兄弟节点地址 .

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

Traversing the tree:

我认为这个算法可以在Depth First中遍历树：
```
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
```
回复于 2024-04-19T07:06:37+08:00

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

2 回答

相关问题