如何使用 elixir 递归地实现二叉搜索树的高度？

Question

我正在使用 Elixir 为二叉搜索树编写一些程序，并且运行进入了一个具有递归计算高度功能的路障。

树高的基本递归公式如下。

如果树为空则 return 0
其他
1. 递归获取左子树的最大深度即，呼叫 maxDepth( tree->left-subtree)
2. 递归获取右子树的最大深度即呼叫 maxDepth( tree->right-subtree)
3. 获取左右最大深度的最大值子树并为当前节点添加 1。 max_depth = max(max dept of left subtree,max depth of right subtree) + 1
4. Return max_depth

就我而言，当我尝试使用通用节点结构测试函数时出现以下错误。

** (ArithmeticError) bad argument in arithmetic expression

我尝试删除 left_depth 和 right_depth 的加法 1。这消除了算术错误，但我也没有得到任何数值结果（高度）来显示。

这是我的高度函数。如您所见，它几乎完全符合递归格式。

# calculate the height
@spec height(bst_node) :: number
def height(node) do
  if is_nil(node) do
    IO.puts "No tree exists. The height is 0"
  else
    left_depth =  height(node.left)
    right_depth = height(node.right)
    if left_depth >= right_depth do
        left_depth + 1
        IO.puts "The height of the tree is #{left_depth + 1}"
    else
      right_depth + 1
      IO.puts "The height of the tree is #{right_depth + 1}"
    end
  end
end

我更希望能够在 elixir 中递归地执行这个高度函数，但如果我不得不求助于非递归方式来完成它，那肯定不是世界末日。这应该只显示通用树的高度。

Answer 1

elixir 的三个特性在实现递归解决方案时非常有用：

参数模式匹配
多功能子句
Tail-call优化

这是一个使用前两个功能的示例解决方案：

defmodule Tree do
  defstruct [:left, :right]

  def height(%Tree{left: nil,  right: nil}),   do: 0
  def height(%Tree{left: nil,  right: right}), do: 1 + height(right)
  def height(%Tree{left: left, right: nil}),   do: 1 + height(left)
  def height(%Tree{left: left, right: right}), do: 1 + max(height(left), height(right))
end

首先，用 left 和 right 定义一个名为 Tree 的结构来表示我们的树。

然后我们定义 height 函数的 4 个子句，该函数使用模式匹配来检查 Tree 的 left 和 right 值。

如果left和right都是nil，那么我们就是一片叶子，可以return高度0
如果children之一是nil，那么我们可以return树的高度non-nil，加上1给自己（当前节点）。
同上
最后一个子句处理 children 都是 non-nil 的情况。那样的话，return两个child人身高的最大值，加上我们自己的1。

请注意，1 + recursive_call() 样式将导致递归调用堆栈，因为它必须跟踪调用堆栈中 child 节点的高度，以便最终执行1 + 操作。我们可以通过将 in-progress 高度作为 acc 累加器参数传递给函数来最小化这一点，并利用 tail-call 优化，这允许编译器减少所需的堆栈帧数一个函数做的最后一件事就是调用它自己。在这种情况下，我们仍然需要计算最后一个子句中两个子树的 max，这意味着在大多数情况下我们不会使用 tail-call，但为了完整性我将其包括在内.:

def height_tailcall(%Tree{left: nil, right: nil}, acc), do: acc

def height_tailcall(%Tree{left: nil, right: right}, acc) do
  height_tailcall(right, acc + 1)
end

def height_tailcall(%Tree{left: left, right: nil}, acc) do
  height_tailcall(left, acc + 1)
end

def height_tailcall(%Tree{left: left, right: right}, acc) do
  max(height_tailcall(left, acc + 1), height_tailcall(right, acc + 1))
end

示例：

def example do
  leaf = %Tree{}
  height1 = %Tree{left: leaf,    right: leaf}
  height2 = %Tree{left: height1, right: height1}
  height3 = %Tree{left: height2, right: height1}
  height4 = %Tree{left: nil,     right: height3}

  IO.inspect(height(leaf),    label: "leaf")
  IO.inspect(height(height1), label: "height1")
  IO.inspect(height(height2), label: "height2")
  IO.inspect(height(height3), label: "height3")
  IO.inspect(height(height4), label: "height4")

  IO.inspect(height_tailcall(leaf, 0), label: "leaf (tail recursion)")
  IO.inspect(height_tailcall(height1, 0), label: "height1 (tail recursion)")
  IO.inspect(height_tailcall(height2, 0), label: "height2 (tail recursion)")
  IO.inspect(height_tailcall(height3, 0), label: "height3 (tail recursion)")
  IO.inspect(height_tailcall(height4, 0), label: "height4 (tail recursion)")

  height4
end

输出：

leaf: 0
height1: 1
height2: 2
height3: 3
height4: 4
leaf (tail recursion): 0
height1 (tail recursion): 1
height2 (tail recursion): 2
height3 (tail recursion): 3
height4 (tail recursion): 4
%Tree{
  left: nil,
  right: %Tree{
    left: %Tree{
      left: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      },
      right: %Tree{
        left: %Tree{left: nil, right: nil},
        right: %Tree{left: nil, right: nil}
      }
    },
    right: %Tree{
      left: %Tree{left: nil, right: nil},
      right: %Tree{left: nil, right: nil}
    }
  }
}

Answer 2

你的例外

** (ArithmeticError) bad argument in arithmetic expression

与您的代码正确与否无关。默认情况下，代码块的值是该块内计算的最后一个表达式。当你说：

  right_depth + 1
  IO.puts "The height of the tree is #{right_depth + 1}"

你的 last 表达式是 IO.puts，所以这就是函数调用返回的内容。

IO.puts 是你的最后一个表达式，它 returns 是一个原子。使用助手 i/1 in IEx:

验证

iex(3)> i(IO.puts "Puts returns an atom")      
Puts returns an atom
Term
  :ok
Data type
  Atom
Reference modules
  Atom
:ok

尝试添加两个原子会导致操作无效。可以在 IEx 中重现确切的消息和错误。

iex(4)> :atom + :atom
** (ArithmeticError) bad argument in arithmetic expression: :atom + :atom
    :erlang.+(:atom, :atom)

如何使用 elixir 递归地实现二叉搜索树的高度？

How do implement height of a binary search tree recursively using elixir?

recursion

elixir

height

binary-search-tree