[julia-users] Re: Recursive data structures with Julia

[hubert_tieying]

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