如何将红黑BST转换为数组？

Question

我想将红黑BST转换成阵列,但出了点问题,我无法弄清楚是什么.以下是我用来执行此操作的代码片段:

public T[] toArray() {
    T[] array = (T[]) Array.newInstance(clazz, count);

    inOrder(root, array, 0);

    return array;
}

private void inOrder(Node<T> node, T[] array, int i) {
    if (node != null) {
        inOrder(node.leftChild(), array, i);
        array[i++] = node.data();
        inOrder(node.rightChild(), array, i);
    }
}

在按照升序从10到200插入数字后,输出看起来像这样(我使用preorder遍历来查看树是否保持平衡):

[80, 40, 20, 10, 30, 60, 50, 70, 120, 100, 90, 110, 140, 130, 160, 150, 170, 180]

但是当我调用toArray()方法时,我得到了这个:

80 120 140 160 170 180 null null null null null null null null null null null null 

我在这做错了什么？

Answer 1

看起来只有根和最右边的孩子才会被复制到数组中.您的i值在每次递归调用中都会更改,但在递归调用结束时不会更新.

假设您的树是:

    80
   /  \
  40  120

你的数组大小为3.

你的第一个电话:

• i是0.
• inOrder与左子女递归调用:
  • i是0.
  • inOrder用左子进行递归调用,即null.
  • 存储元素40的元素0,增加i至1.
  • inOrder用正确的孩子递归呼叫,这是null.
  • 返回.
• 这里,i是0依旧!
• 存储元素80的元素0,增加i至1.
• inOrder与正确的孩子递归呼叫:
  • i是1.
  • inOrder用左子进行递归调用,即null.
  • 存储元素120的元素1,增加i至2.
  • inOrder用正确的孩子递归呼叫,这是null.
  • 返回.
• 返回.

结果是[80, 120, null].

让每个递归调用返回其调用者return的值i,以便i在所有递归级别保持更新.

private int inOrder(Node<T> node, T[] array, int i) {
    if (node != null) {
        i = inOrder(node.leftChild(), array, i);
        array[i++] = node.data();
        i = inOrder(node.rightChild(), array, i);
    }
    return i;
}