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

Question

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

"normal" 顺序访问的伪代码：

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
}

示例：给定以下树

上面的算法应该输出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

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

下面的代码是用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
}

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

Saving the in-order visit of a binary tree in an array

algorithm

binary-tree

inorder

binary-search-tree