Julia中的树形数据结构

Question

我需要在Julia中实现一个简单（但不是二进制）的树形结构。基本上，每个节点都需要有一个整数ID，并且我需要一种方便的方法来获取节点的子节点列表以及通过ID向现有节点添加子节点。

例如，0->1->(2->(3,4,5),6)

其中每个数字代表一个节点，我需要函数children(2)和add(7作为4的子节点)。

我知道其他语言可以找到类似的树形结构实现，但我对面向对象编程/类/数据结构还比较新手，无法将它们“翻译”成Julia。

- Waldquelle

---

一棵树可以看作是有向图的特例。而有向图则在 Graphs.jl 和 LightGraphs.jl 中实现。但也许使用专门的数据结构会更好。 - Dan Getz

除了 Graphs.jl 的第一次编译之外，这个方法比专门的数据结构慢的原因是什么？ - Waldquelle

Answer 1

您没有说明您希望ID在添加新节点时自动分配，还是在添加子节点时要指定它们的ID（这需要进行某种形式的更复杂的查找）。 如果可以自动生成ID，则可以按以下方式实现树形结构：

type TreeNode
    parent::Int
    children::Vector{Int}
end
type Tree
    nodes::Vector{TreeNode}
end
Tree() = Tree([TreeNode(0, Vector{Int}())])
function addchild(tree::Tree, id::Int)
    1 <= id <= length(tree.nodes) || throw(BoundsError(tree, id))
    push!(tree.nodes, TreeNode(id, Vector{}()))
    child = length(tree.nodes)
    push!(tree.nodes[id].children, child)
    child
end
children(tree, id) = tree.nodes[id].children
parent(tree,id) = tree.nodes[id].parent

否则，您可能想使用Dict{Int,TreeNode}来存储树节点。

- Scott Jones

---

谢谢，这非常有帮助。我后来意识到我永远不需要向树添加新的子节点，只需要将它们重新分配给其他节点即可，但这似乎可以通过对您的addchild()进行小修改来实现。 - Waldquelle

nodes 作为 Dict 类型是否更好？这样可以更轻松/更便宜地添加/删除/修改树结构。 - Imanol Luengo

相对于简单的向量，Dict可能非常昂贵。例如，您可以通过将父节点设置为-1来标记上述结构中删除的TreeNode，并在读取时进行检查，以便轻松删除节点。但这真的取决于用例。正如我在答案中所说，如果ID已分配，则应使用Dict {Int，TreeNode}。 - Scott Jones