Am Donnerstag, 27. Oktober 2016 16:03:27 UTC+2 schrieb Ángel de Vicente:
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
>
> Here is a variant for a binary search tree which uses union types and
also has an empty tree. The definition is straightforward and - at least
for me - easy to understand.
type Empty
end
et = Empty() # a possible variant for an empty tree
typealias BT{T} Union{T, Empty}
type BTree
key::Int
left:: BT{BTree}
right::BT{BTree}
end
BST = BT{BTree} # type of binary search trees
BTree(key::Int) = BTree(key, et, et):: BST
function insert(t::BST, val)
if t == et
return BTree(val)
elseif val < t.key
return BTree(t.key, insert(t.left,val), t.right)
else
return BTree(t.key, t.left, insert(t.right,val))
end
end
# Testing:
# arr = [9,15,-4,3,11,6,-2,-16]
# tr = et
# for a in arr
# tr = insert(tr,a)
# end
# tr
