154 lines
4.3 KiB
Elixir
154 lines
4.3 KiB
Elixir
import Kernel, except: [length: 1]
|
|
|
|
defmodule MbBinaryTree do
|
|
@moduledoc """
|
|
Documentation for `MbBinaryTree`.
|
|
"""
|
|
|
|
@type t :: nil | nonempty_maybe_improper_list()
|
|
|
|
@spec new(any) :: t
|
|
@doc """
|
|
Create a new tree with a root node.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.new(4)
|
|
[4, nil, nil]
|
|
|
|
"""
|
|
def new(root) do
|
|
[root, nil, nil]
|
|
end
|
|
|
|
@spec is_tree?(any) :: boolean
|
|
@doc """
|
|
Test whether argument is a valid binary tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.new(19) |> MbBinaryTree.is_tree?()
|
|
true
|
|
iex> MbBinaryTree.is_tree?([12])
|
|
false
|
|
iex> MbBinaryTree.is_tree?(12)
|
|
false
|
|
iex> MbBinaryTree.is_tree?([12, [4, MbBinaryTree.new(2), MbBinaryTree.new(5)], [26, MbBinaryTree.new(14), [28, MbBinaryTree.new(27), MbBinaryTree.new(30)]]])
|
|
"""
|
|
def is_tree?(nil), do: true
|
|
def is_tree?([_, nil, nil]), do: true
|
|
def is_tree?([_, nil, right]), do: is_tree?(right)
|
|
def is_tree?([_, left, nil]), do: is_tree?(left)
|
|
def is_tree?([_, left, right]), do: is_tree?(left) && is_tree?(right)
|
|
def is_tree?(_), do: false
|
|
|
|
@spec is_empty?(t) :: boolean
|
|
@doc """
|
|
Check if a binary tree is empty.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.is_empty?(nil)
|
|
true
|
|
iex> MbBinaryTree.new("hello") |> MbBinaryTree.is_empty?()
|
|
false
|
|
"""
|
|
def is_empty?(nil), do: true
|
|
def is_empty?(_), do: false
|
|
|
|
@spec length(t) :: non_neg_integer
|
|
@doc """
|
|
Get the length of a tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.length([1, MbBinaryTree.new(2), MbBinaryTree.new(3)])
|
|
3
|
|
iex> MbBinaryTree.length([12, [4, MbBinaryTree.new(2), MbBinaryTree.new(5)], [26, MbBinaryTree.new(14), [28, MbBinaryTree.new(27), MbBinaryTree.new(30)]]])
|
|
9
|
|
"""
|
|
def length([_ | [left, right]]), do: 1 + length(left) + length(right)
|
|
def length(_), do: 0
|
|
|
|
@doc """
|
|
Calculate the depth of a binary tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.depth(nil)
|
|
0
|
|
iex> MbBinaryTree.depth([1, nil, nil])
|
|
1
|
|
iex> MbBinaryTree.depth([1, [2, nil, nil], [3, nil, nil]])
|
|
2
|
|
iex> MbBinaryTree.depth([1, [2, nil, nil], [3, [4, nil, nil], [5, nil, nil]]])
|
|
3
|
|
iex> MbBinaryTree.depth([12, [4, MbBinaryTree.new(2), MbBinaryTree.new(5)], [26, MbBinaryTree.new(14), [28, MbBinaryTree.new(27), MbBinaryTree.new(30)]]])
|
|
4
|
|
"""
|
|
def depth(tree) do
|
|
case tree do
|
|
nil -> 0
|
|
[_, nil, nil] -> 1
|
|
[_, left, right] -> 1 + max(depth(left), depth(right))
|
|
end
|
|
end
|
|
|
|
@spec left(t) :: t
|
|
@doc """
|
|
Get the left child of a tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.left([1, MbBinaryTree.new(2), MbBinaryTree.new(3)])
|
|
[2, nil, nil]
|
|
iex> MbBinaryTree.new(12) |> MbBinaryTree.left()
|
|
nil
|
|
iex> MbBinaryTree.left([12, [4, MbBinaryTree.new(2), MbBinaryTree.new(5)], [26, MbBinaryTree.new(14), [28, MbBinaryTree.new(27), MbBinaryTree.new(30)]]])
|
|
[4, [2, nil, nil], [5, nil, nil]]
|
|
"""
|
|
def left([_, left | _]), do: left
|
|
def left(_), do: nil
|
|
|
|
@spec right(t) :: t
|
|
@doc """
|
|
Get the right child of a tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.right([1, MbBinaryTree.new(2), MbBinaryTree.new(3)])
|
|
[3, nil, nil]
|
|
iex> MbBinaryTree.new(12) |> MbBinaryTree.right()
|
|
nil
|
|
iex> MbBinaryTree.right([12, [4, MbBinaryTree.new(2), MbBinaryTree.new(5)], [26, MbBinaryTree.new(14), [28, MbBinaryTree.new(27), MbBinaryTree.new(30)]]])
|
|
[26, [14, nil, nil], [28, [27, nil, nil], [30, nil, nil]]]
|
|
"""
|
|
def right([_, _, right]), do: right
|
|
def right(_), do: nil
|
|
|
|
@spec update_left(t, t) :: t
|
|
@doc """
|
|
Update the left child of a tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.update_left([1, MbBinaryTree.new(2), MbBinaryTree.new(3)], MbBinaryTree.new(4))
|
|
[1, [4, nil, nil], [3, nil, nil]]
|
|
iex> MbBinaryTree.new(12) |> MbBinaryTree.update_left(MbBinaryTree.new(4))
|
|
[12, [4, nil, nil], nil]
|
|
"""
|
|
def update_left([node, _left, right], new_left), do: [node, new_left, right]
|
|
|
|
@spec update_right(t, t) :: t
|
|
@doc """
|
|
Update the right child of a tree.
|
|
|
|
## Examples
|
|
|
|
iex> MbBinaryTree.update_right([1, MbBinaryTree.new(2), MbBinaryTree.new(3)], MbBinaryTree.new(4))
|
|
[1, [2, nil, nil], [4, nil, nil]]
|
|
iex> MbBinaryTree.new(12) |> MbBinaryTree.update_right(MbBinaryTree.new(4))
|
|
[12, nil, [4, nil, nil]]
|
|
"""
|
|
def update_right([node, left, _right], new_right), do: [node, left, new_right]
|
|
end
|