具有树遍历功能的Stack_overflow

Question

我的树定义如下：(只是为了更好地理解，我的数据类型要复杂得多。)

  type tree = {
    mutable value : int;
    mutable nodes : tree list
  }

我需要找到一个0和1的序列，如下所示：

    1  
    |
  0 0
  \ /
   1
   |
   1

输出将是根以及0和1的序列。下面是我的代码：(我假设该序列仅在值为0的树的节点(树列表)只有一个元素时出现，但我需要更改这一点，因为这是不必要的。)

let rec getSequence tree = 
  match tree.value with
  | 0 ->
if (List.length tree.nodes) = 1 then
  let nextTree = List.hd tree.nodes in
  match nextTree.value with
  | 1 -> 
    nextTree.nodes <- [];
    tree.nodes <- [nextTree];
    [tree]
  | 0 -> List.concat (List.map (fun t -> getSequence t) nextTree.nodes)
else List.concat (List.map (fun t -> getSequence t) tree.nodes)
  | 1 -> List.concat (List.map (fun t -> getSequence t) tree.nodes)

由于某些原因，当我执行代码时，异常Stack_overflow被抛出。有人能帮我吗？

Answer 1

let nextTree = List.hd tree.nodes in
nextTree.nodes <- [];

不等同于：

tree.nodes<-(List.tl tree.nodes);

对于第一个，树不会更改它包含的列表，所以您总是执行相同的操作，并且您有一个stack_overflow

Answer 2

我试过了，但是你的样例输入也没有异常。我猜只有输入更大(特别是更深)的时候才会出现Stack_overflow异常。

以下是一些选项：

1. 增加堆栈大小：

export OCAMLRUNPARAM='l=64M‘#或者whatever

• Rewrite你的函数是尾递归的，所以它不需要太多的堆栈空间。您可以通过将状态作为参数传递来实现此目的。

其他建议：

• 使用模式匹配而不是List.length，你可以使用2.，你也可以避免使用List.concat。