java - 在不使用额外数据结构的情况下从 BST 检索值的排序数组

Question

我已经使用 List/ArrayList 找到了类似问题的答案，但是我最大的问题是我试图不使用数组以外的任何数据结构。有没有办法迭代 BST，将值按顺序添加到数组中？

更多关于这个问题的信息 - 我有一个 BST，从技术上讲它是一个 TreeMap，所以它有一个 root.value 和 root.index，两者都是唯一的。 root.index 表示元素添加的顺序。我需要按升序返回索引的 int[](按 root.value)。

    public int[] getDataInOrder( ){
        int[] orderedArray = new int[neededSize];
        getDataInOrder(overallRoot, 0, orderedArray);
        return orderedArray;
    }

    private void getDataInOrder(TreeNode<E> root, int indexOfArray, int[] orderedArray){
        if (root != null){
            getDataInOrder(root.left, indexOfArray, orderedArray);
            orderedArray[indexOfArray] = root.index;
            indexOfArray++;
            getDataInOrder(root.right, indexOfArray, orderedArray);
        }
    } 

创建一棵树

    UniqueIndex<Integer> intTree = new UniqueIndex<>();
    intTree.add(5);
    intTree.add(7);
    intTree.add(-15);
    intTree.add(3);
    intTree.add(1);
    intTree.add(6);
    intTree.add(10);

输出应该是[2, 4, 3, 0, 5, 1, 6]，但它是[0, 1, 6, 0, 0, 0 ，0]。我觉得问题在于 indexOfArray/传递它，并由于通过引用传递而将元素添加到数组后进行更新，但我无法指出它。任何帮助将不胜感激。

Answer 1

您可以做的是将排序后的索引数组从函数调用参数中取出，即不将其作为参数并在更高的范围中使用它。然后保留一个变量，其中包含数组中当前填充元素的索引。

之后，只需执行一次中序遍历，并将根索引分配给排序索引数组中的下一个空槽，然后递增已填充槽计数器。

您的错误在于将数组作为函数参数传递，就像 @RealSkeptic 指出的那样。

你可以这样做:

    private int[] orderedArray = new int[neededSize];
    private int currentElement = 0;

    public int[] getDataInOrder( ){
         getDataInOrder(overallRoot);
         return orderedArray;
    }

    private void getDataInOrder(TreeNode<E> root){
         if (root != null){
           getDataInOrder(root.left);
           orderedArray[currentElement] = root.index;
           currentElement++;
           getDataInOrder(root.right);
        }
    }