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

Question

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

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

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

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

**（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的left和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}
    }
  }
}

Answer 2

你的例外

**（ArithmeticError）算术表达式中的错误参数

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

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

你的最后一个表达式是IO.puts，这是函数调用返回的结果。

IO.puts是你的最后一个表达式，它返回一个原子。使用帮助器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)