Hi, I've been trying to implement some code to build Binary Search Trees. The code below works, I'm able to build a tree and then print it in ascending order, but it is quite ugly, with those Nullable types and having to access subtrees with code like tree.value.left instead of directly tree.left
Being used to nullify a pointer for this, I'm not sure how to best proceed in Julia. Is there a better way to build recursive data structures? (I read the section on "Incomplete Initialization" at http://docs.julialang.org/en/release-0.5/manual/constructors/, but I'm not sure I can use the idea in there, since I want some elements of the tree to point to nothing, not to some other element in the tree.) Many thanks, Ángel de Vicente ,---- | julia> include("bst.jl") | b | | julia> tree = b.build_bst([10,2,4,8,2]) | Dropping 2. No repeated values allowed | Nullable{b.Bst}(b.Bst(10,b.Bst(2,#NULL,b.Bst(4,#NULL,b.Bst(8,#NULL,#NULL))),#NULL)) | | julia> b.print_bst(tree) | 2 | 4 | 8 | 10 | | julia> `---- ,---- | module b | | type Bst | val::Int | left::Nullable{Bst} | right::Nullable{Bst} | end | Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}()) | | "Given an array of Ints, it will create a BST tree, type: Nullable(Bst)" | function build_bst(list::Array{Int,1}) | head = list[1] | tree = Nullable(Bst(head)) | for e in list[2:end] | place_bst(tree,e) | end | return tree | end | | "Adds element 'e' in the BST 'tree' (which cannot be a NULL BST)" | function place_bst(tree::Nullable{Bst},e::Int) | if e == tree.value.val | println("Dropping $(e). No repeated values allowed") | elseif e < tree.value.val | if (isnull(tree.value.left)) | tree.value.left = Nullable(Bst(e)) | else | place_bst(tree.value.left,e) | end | else | if (isnull(tree.value.right)) | tree.value.right = Nullable(Bst(e)) | else | place_bst(tree.value.right,e) | end | end | end | | "Prints a BST (does not accept a NULL BST as input)" | function print_bst(tree::Nullable{Bst}) | if !isnull(tree.value.left) print_bst(tree.value.left) end | println(tree.value.val) | if !isnull(tree.value.right) print_bst(tree.value.right) end | end | | end `---- -- Ángel de Vicente http://www.iac.es/galeria/angelv/
