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

Question

我正在使用 Elixir 为二叉搜索树编写一些程序，但遇到了一个带有递归计算高度函数的障碍。

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

1. 如果树为空则返回 0

2. 别的

   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. 返回最大深度

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

** (ArithmeticError) 算术表达式中的错误参数

我尝试将 1 添加到 left_depth 和 right_depth 中。这消除了算术错误，但我也没有得到任何数字结果（高度）显示。

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

# 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 的三个特性在实现递归解决方案时非常有用：

1. 参数模式匹配
2. 多函数子句
3. 尾调用优化

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

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

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

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

1. 如果两个left和right是nil，那么我们是叶并且可以返回高度0
2. 如果其中一个孩子是nil，那么我们可以返回非零树的高度，加上1自己（当前节点）。
3. 和上面一样。
4. 最后一个条款处理两个孩子都非零的情况。在这种情况下，返回两个孩子身高的最大值，加上我们1自己。

请注意，该1 + recursive_call()样式将导致递归调用堆栈，因为它必须跟踪调用堆栈中子节点的高度才能最终执行1 +操作。我们可以通过将进行中的高度作为acc累加器参数传递给函数，并利用尾调用优化来最小化这种情况，这允许编译器减少函数所做的最后一件事时所需的堆栈帧数称自己。在这种情况下，我们仍然需要计算max最后一个子句中两个子树的

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}
    }
  }
}