二叉树操作搜索匹配的递归调用

Question

我遇到了在二叉树中搜索值并返回该驻留值的节点的问题的解决方案。因此，时间复杂度预计为 O(n)。

这是我解决问题的方法：

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) when x = root -> tree
  | Node (_, left, right) ->
    match left with
    | Empty -> search x right
    | t -> search x t

这是我找到的解决方案，但我认为我的解决方案更有效率和可读性：

let rec search x t =
  match t with
  | Empty -> Empty
  | Node(v, l, r) ->
    if v = x then t
    else 
      match search x l with
      | Empty -> search x r
      | t' -> t'

我的解决方案更好还是我遗漏了什么？

供参考，

tree

类型的定义：

type 'a tree = 
  | Empty
  | Node of 'a * 'a tree * 'a tree

Answer 1

这些在功能上不等同。

如果左分支本身是

Empty

，你的函数只会搜索右分支，如果搜索那个分支的结果是

Empty

.

考虑：

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Empty

你的意思可能是：

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, _, _) when x = root -> tree
  | Node (_, left, right) ->
    match search x left with
    | Empty -> search x right
    | t -> t

现在：

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Node (4, Empty, Empty)

另一个想法是，您可能想要创建一个

search_opt

函数，它返回一个

option

类型，其中

None

表示没有找到匹配项。

let rec search_opt x = 
  function 
  | Empty -> None
  | Node (root, _, _) as tree when x = root -> Some tree
  | Node (_, left, right) ->
    match search_opt x left with
    | None -> search_opt x right
    | t -> t