如何使用长生不老药递归地实现二叉搜索树的高度?

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

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

如果树为空，则返回 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. 返回max_depth

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

**(算术错误

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

我尝试删除 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 有三个非常有用的功能：

参数模式匹配
多个功能子句
尾部调用优化

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

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值。

如果left和right都是nil，那么我们是一片叶子，可以返回高度0
如果其中一个子节点是nil，那么我们可以返回非 nil 树的高度，加上我们自己的1(当前节点)。
同上。
最后一项涉及两个孩子都不是零的情况。在这种情况下，返回两个孩子的身高最大值，加上我们自己的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}
}
}
}

您的例外

**(算术错误

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

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

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

你的最后一个表达式是 IO.puts，所以这就是从函数调用返回的内容。

IO.puts是你的最后一个表达式，它返回一个原子。使用 IEx 中的帮助程序 i/1 验证：

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)

相关内容

最新更新

热门标签：