2

在 OCaml 中编写递归中序遍历很容易，但是如何编写迭代呢？与for loop或while？

4

2 回答 2

4

要求某人在没有递归调用的情况下编写一些东西是愚蠢的，但我仍然会这样做，因为这是一个有趣的练习。从递归到迭代总是相同的过程。

type tree = Leaf | Node of int * tree * tree

let rec in_order = function
  | Leaf -> []
  | Node(i,l,r) -> in_order l @ (i :: in_order r);;

好了，现在我们有了递归函数。第一步是将其转换为尾递归。这实际上是最困难的一步，因为它需要真正的逻辑和算法更改。

我们将为包含计算结果的函数添加一个新参数：

 let rec ino res = function
  | Leaf -> ()
  | Node(i,l,r) -> 
    begin
      ino res r ;
      res := i :: !res ;
      ino res l
    end

最后，结果是!res。

现在我们有了这个，移除递归调用就很容易了，我们只需要考虑编译器在递归调用时会做什么。好吧，它只是在将函数的参数和下一个要执行的工作放入堆栈之后执行一个 while 循环。让我们去做吧。

open Stack
type work = Value of int | NextNode of tree ref

let ino t : int list =
  let res = ref [] in
  let stack = Stack.create () in
  push (NextNode (ref t)) stack;
  try
    while true do
      let current = pop stack in
      match current with 
      Value i -> res := i :: !res
    | NextNode n ->
      begin
        match !n with
        Leaf -> ()
          | Node(i,l,r) -> 
        begin
          push (NextNode (ref l)) stack;
          push (Value i) stack;
          push (NextNode (ref r)) stack
        end
      end
    done;
    assert false
  with
    | Empty -> !res

在这里，我们只记得接下来要做的事情。我们知道，当我们到达一个节点时，我们必须处理它的右孩子，然后是节点的值，然后是它的左孩子，所以我们只是把所有这些都放在堆栈中（当然是相反的顺序），我们继续堆栈的下一个元素。当堆栈为空时，我们已经访问了整棵树，我们可以返回。

我希望这篇文章能够让一些人相信递归比迭代编程更强大。3 行与 26 行。QED。

于 2013-08-13T15:29:27.547 回答
0

这是迭代有序遍历的另一种观点：

type 'a node = {mutable data: 'a;
                mutable left : 'a node option;
                mutable right: 'a node option; }

let new_node data = {data; left = None; right = None;}

let insert tree new_data =
  let module Wrapper = struct exception Stop_loop end in
  let iter = ref tree in
  try
    while true do
      if new_data < !iter.data
      then match !iter.left with
        | None ->
          !iter.left <- Some (new_node new_data);
          raise Wrapper.Stop_loop
        | Some left_tree -> iter := left_tree
      else if new_data > !iter.data
      then match !iter.right with
        | None ->
          !iter.right <- Some (new_node new_data);
          raise Wrapper.Stop_loop
        | Some right_tree -> iter := right_tree
    done
  with Wrapper.Stop_loop -> ()

let in_order_traversal tree =
  let module W = struct exception Stop_loop end in
  let visited_stack = Stack.create () in
  let iter_node = ref (Some tree) in
  try while true do
      (* Inner loop, we keep trying to go left *)
      (try while true do
           match !iter_node with
           | None -> raise W.Stop_loop
           | Some left ->
             Stack.push left visited_stack;
             iter_node := left.left
         done;
       with W.Stop_loop -> ());

      (* If we have no more to process in the stack, then we're
         done *)
      if Stack.length visited_stack = 0
      then raise W.Stop_loop
      else
        (* Here we're forced to start moving rightward *)
        let temp = Stack.pop visited_stack in
        Printf.sprintf "%s " temp.data |> print_string;
        iter_node := temp.right
    done
  with W.Stop_loop -> ()

let () = 
  let root = new_node "F" in

  ["B";"G";"A";"D";"I";"C";"E";"H"] |> List.iter (insert root);
  in_order_traversal root;
  print_newline ();
于 2016-07-18T00:12:32.600 回答