将BST转换为数组

Question

我看了一遍,似乎无法找到任何帮助..对于一个学校项目,我有一个BST树,我必须将所有从树中的整数放入一个名为BSTarray的int数组.
这是我到目前为止:

public int [] toBSTArray() {
    int size = 20;
    int [] BSTarray = new int [size];
    for(int i = 0; i <size; i++) {
        makeArray(root);
        BSTarray[i] = root.getValue();
}

    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node) {
    if (node != null) {
        makeArray(node.getLeft());
        makeArray(node.getRight());
        // System.out.print(node.getValue() + " ");
    }
}

我认为这个方法应该通过树并将它找到的值添加到BSTarray中的不同索引中,但它所做的只是将相同的数字添加到数组中的所有索引中.我在递归时做错了吗？

Answer 1

试试这个:

Integer[] values = extractValues(n).toArray(new Integer[] {});

使用该方法定义:

private static List<Integer> extractValues(Node n) {
    List<Integer> result = new ArrayList<>();
    if (n.getLeft() != null) {
        result.addAll(extractValues(n.getLeft()));
    }

    if (n.getRight() != null) {
        result.addAll(extractValues(n.getRight()));
    }

    result.add(n.getValue());

    return result;
}

我假设一个类似于你的节点结构.当然,如果不以静态方式使用它,则该方法不必是静态的.

由于列表转换,此方法可能不是最有效的方法,但您不必担心任何数组大小.如果你真的需要函数来返回一个数组,只需将它包装到另一个函数中,或者让建议的函数返回一个数组(这将使得必须在每次返回之前将列表转换为数组).

关于你的代码,你迭代遍历i整个数组(无论你知道它的大小),但你总是将值设置为根节点的值.这就是为什么你总是拥有相同的价值.您的makeArray函数以递归方式调用自身,但它不执行任何操作(即使您添加了一个sysout语句;))

更新:

并且对于不使用列表的约束,这里是另一个仅使用数组的版本:

int size = 20;
int[] results = new int[size];
extractValues(n, results, 0);

方法定义:

private static int extractValues(Node n, int[] results, int index) {
    if (n.getLeft() != null) {
        index = extractValues(n.getLeft(), results, index);
    }

    if (n.getRight() != null) {
        index = extractValues(n.getRight(), results, index);
    }

    results[index] = n.getValue();

    return index + 1;
}

注意,结果将是results,然后.大小必须假定为节点数量较大,或者必须先通过遍历树来计算.