3

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

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 中的不同索引中，但它所做的只是将相同的数字添加到数组中的所有索引中。我在递归上做错了吗？

4

2 回答 2

6

试试这个：

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, 中。大小必须被假定为大于节点的数量，或者必须通过遍历树来计算，之前。

于 2012-12-13T23:24:27.067 回答
3

这个怎么样：（您的递归不会对数组进行任何更改）

public int [] toBSTArray() {
    int size = 20; //ASSUMING THIS IS LESS THAN OR EQUAL TO NUMBER OF NODES IN THE TREE
    int [] BSTarray = new int [size];
    makeArray(root, 0, BSTarray);
    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node, int i, int [] BSTarray ) {
    if (node != null) {
        BSTarray[i] = root.getValue();   
        makeArray(node.getLeft(), 2*i+1, BSTarray);
        makeArray(node.getRight(), 2*i+2, BSTarray);
   }
}
于 2012-12-13T23:53:08.287 回答