💨

木構造の高さを求める

2024/04/01に公開

木構造の高さを求めます。

実装

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

function insert(root::Union{Node, Nothing}, key::Int)::Node
    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

function heights(node::Union{Node, Nothing})::Int
    if node === nothing
        return 0
    end

    left_height = heights(node.left)
    right_height = heights(node.right)

    return 1 + max(left_height, right_height)
end

root = insert(nothing, 12)

insert(root, 10)
insert(root, 15)

insert(root, 8)

@show heights(root)
@show heights(root.left)
@show heights(root.right)

結果

yuu@penguin:~/yatai$ julia nagai.jl 
heights(root) = 3
heights(root.left) = 2
heights(root.right) = 1

Discussion