Hi,
by searching in the web I found
(http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia)
a way to make my BST code much cleaner (as posted below). Nevertheless,
I don't find this very ellegant, since the head node is of type Bst,
while the children are of type Nullable{Bst} (is this the 'canonical' way
of building recursive data structures with Julia?).
But when I first read the code in SO, I thought that it was probably
wrong, since it does:
node.left = BST(key)
where node.left is of type Nullable{BST}.
Then I realized that automatic conversion from BST to Nullable{BST} is
done when assigning to node.left, so all is good. Coming from Fortran,
this is a bit odd for me... what are the rules for automatic conversion?
Thanks a lot,
Ángel de Vicente
,----
| 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: Bst"
| function build_bst(list::Array{Int,1})
| head = list[1]
| tree = Bst(head)
| for e in list[2:end]
| place_bst(tree,e)
| end
| return tree
| end
|
| function place_bst(tree::Bst,e::Int)
| if e == tree.val
| println("Dropping $(e). No repeated values allowed")
| elseif e < tree.val
| if (isnull(tree.left))
| tree.left = Bst(e)
| else
| place_bst(tree.left.value,e)
| end
| else
| if (isnull(tree.right))
| tree.right = Bst(e)
| else
| place_bst(tree.right.value,e)
| end
| end
| end
|
| function print_bst(tree::Bst)
| if !isnull(tree.left) print_bst(tree.left.value) end
| println(tree.val)
| if !isnull(tree.right) print_bst(tree.right.value) end
| end
|
| end
`----
,----
| julia> include("bst.jl")
|
| julia> b.print_bst( b.build_bst([4,5,10,3,20,-1,10]))
| Dropping 10. No repeated values allowed
| -1
| 3
| 4
| 5
| 10
| 20
|
| julia>
`----
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/
