💡

2分探索木を作成する

2024/03/28に公開

根ノードからの挿入によって2分探索木を作成します。

実装

mutable struct Node
    key::Int
    left::Union{Node, Nothing}
    right::Union{Node, Nothing}
end

function insert(root, key)
    if root === nothing
        root = Node(key, nothing, nothing)
    elseif root.key > key
        root.left = insert(root.left, key)
    elseif root.key < key
        root.right = insert(root.right, key)
    end

    return root
end


root = insert(nothing, 6)

insert(root, 3)
insert(root, 1)
insert(root, 5)

insert(root, 9)

@show root

標準出力は、次の通りです。

yuu@penguin:~/yatai$ julia ueda.jl 
root = Node(6, Node(3, Node(1, nothing, nothing), Node(5, nothing, nothing)), Node(9, nothing, nothing))

Discussion