在数组中保存二叉树的有序访问

Question

问题如下：在给定二叉树T和一个数组的情况下，是否存在一种算法，允许将该树的相应有序访问结果存储在数组中？

“正常”有序访问的伪代码：

inOrder(x){ // x is a node of a binary tree
   if(x != NIL){ // the node is not null
      inOrder(x.left)
      print(x.key)
      inOrder(x.right)
   }
}

// Function calling inOrder
printInOrder(T){ // T is a binary tree
   inOrder(T.root) // T.root is the root of the tree
}

示例：鉴于以下树

     5 
   /   \
  3     8
 / \   / 
2   7 1   

以上算法应输出2 3 7 5 1 8。

我确信这可以实现，应该不会太难，但是我目前正在为这个问题而苦苦挣扎。

Answer 1

首先关于数组：要填充数组，您需要事先知道数组的长度。如果您不需要指定实例化数组的长度（取决于您使用的语言），则实际上不是数组。它是一种动态数据结构，其语言实现会自动增加其大小。

现在，我假设您事先不知道树的大小。如果您知道大小，则可以实例化指定大小的数组。假设您不知道数组的大小，则需要使用动态数据结构，例如Java中的ArrayList。

因此，在代码中的每个print(x.key)处，只需将x.key附加到列表中即可（例如list.add(x.key)）。遍历完成后，可以将List转到array。

您也可以使用遍历的iterative版本。

递归方法的一个简单解决方案是使用单个元素数组来跟踪索引，例如：

void inOrder(x, int[] idx, int[] arr):
    if x != NIL:
       inOrder(x.left, idx, arr)
       arr[idx[0]++] = x.key
       inOrder(x.right, idx, arr)

尽管我敢肯定，还有其他方法可能会变得很麻烦（也许）。无论如何，我还是喜欢迭代版本。

Answer 2

写入数组（而不是打印）意味着您需要跟踪要在数组中写入哪个索引。如果您需要在数组本身之外没有任何可变状态的情况下执行此操作，则需要将当前索引作为参数传递，并返回新的当前索引。

下面的代码用static single assignment form编写，因此即使局部变量也不会发生突变。如果这不是必需的，则可以对代码进行一些简化。我假设数组长度是已知的；如果需要计算，那是一个单独的问题。

inOrder(x, arr, i) {
    if(x == NIL) {
        return i
    } else {
        i2 = inOrder(x.left, arr, i)
        arr[i2] = x.key
        i3 = inOrder(x.right, arr, i2 + 1)
        return i3
    }
}

getArrayInOrder(T, n) {
    arr = new array of length n
    inOrder(T.root, arr, 0)
    return arr
}

Answer 3

如果您的语言/用例允许将整数放入数组中，则可以将索引存储在数组中。我要倒退，因为那样会更简单：

inOrder(x, arr){
   if(x != NIL){
      inOrder(x.right)
      arr[--arr[0]] = x.key
      inOrder(x.left)
   }
}

saveInOrder(T, n){
   arr = new int[n]
   arr[0] = n
   inOrder(T.root, arr)
   return arr
}