💨
木構造の高さを求める
木構造の高さを求めます。
実装
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