Tree data structure in Julia

Question

I need to implement a simple (but not binary) tree in Julia. Basically, each node needs to have an integer ID, and I need a convenient way to get a list of children for a node + add child to an existing node by ID.

e.g. 0->1->(2->(3,4,5),6)

where each number represents a node, I need the functions children(2) and add(7 as child of 4).

I am aware that similar tree implementations can be found for other languages, but I am pretty new to OOP/classes/data structures and not managing to "translate" them to Julia.

Answer 1

You didn't state whether you want the IDs to be assigned automatically as new nodes are added, or if you want to specify them when you add the children (which would involve some form of more complicated lookup). If the IDs can be assigned, you could implement a tree structure as follows:

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

Otherwise, you might want to use Dict{Int,TreeNode} to store the tree nodes.