如何将红黑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 的数字后，输出如下所示（我使用前序遍历来查看树是否保持平衡）：

[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

看起来只有根和 right-most children 被复制到数组中。您的 i 值在每次递归调用中都在更改，但在递归调用结束时不会更新。

假设你的树是：

    80
   /  \
  40  120

您的数组大小为 3。

您的第一个电话：

i 是 0.
用左 child 递归调用 inOrder：
- i 是 0.
- 用左child递归调用inOrder，即null。
- 将元素 40 存储在元素 0，将 i 增加到 1。
- 用右child递归调用inOrder，即null.
- Return.
这里，i还是0！
将元素 80 存储在元素 0，将 i 增加到 1。
用右 child 递归调用 inOrder：
- i 是 1.
- 用左child递归调用inOrder，即null。
- 将元素 120 存储在元素 1，将 i 增加到 2。
- 用右child递归调用inOrder，即null.
- Return.
Return.

结果是[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;
}

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

How to convert a red black BST into an array?

java

red-black-tree

data-structures