java - 将 BST 转换为数组

Question

我找遍了，似乎找不到任何帮助。对于一个学校项目，我有一个 BST 树，我必须将树中的所有整数放入一个名为 BSTarray 的整数数组中。< br/> 这是我目前所拥有的:

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 以填充整个数组(无论您从哪里知道大小)但您始终将值设置为根节点的值。这就是为什么你总是有相同的值(value)。您的 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 中，然后。必须假设大小大于节点数，或者必须在之前通过遍历树来计算大小。