java 将 BST 转换为数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13870118/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
converting BST to array
提问by Gcap
I've looked all over and can't seem to find any help for this.. for a school project I have a BST tree and I have to put all the ints from the tree into an int array called BSTarray.
This is what I have so far:
我已经查看了所有内容，似乎找不到任何帮助。对于一个学校项目，我有一个 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() + " ");
}
}
I thought this method was supposed to go through the tree and add in the values it finds into different indexes in the BSTarray, but all it's doing is adding the same number into all the indexes in the array. Am I doing something wrong with the recursion?
我认为这个方法应该遍历树并将它找到的值添加到 BSTarray 中的不同索引中，但它所做的只是将相同的数字添加到数组中的所有索引中。我在递归上做错了吗？
回答by sebastian_oe
Try this:
试试这个：
Integer[] values = extractValues(n).toArray(new Integer[] {});
with that method definition:
使用该方法定义：
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 assumed a node structure that is similar to yours. Of course, the method doesn't have to be static if you don't use it in a static way.
我假设了一个与您类似的节点结构。当然，如果您不以静态方式使用它，则该方法不必是静态的。
This method might not be the most efficient due to the list conversion but you don't have to bother with any array sizes. If you really need the function to return an array, just wrap it into another function or let the proposed function return an array (this would make it necessary to convert the list to an array before each return).
由于列表转换，此方法可能不是最有效的，但您不必担心任何数组大小。如果您确实需要该函数返回一个数组，只需将其包装到另一个函数中或让建议的函数返回一个数组（这将使得在每次返回之前必须将列表转换为数组）。
Concerning your code, you iterate over the ito fill the entire array (no matter where you know the size from) but you always set the value to the value of the root node. That's why you always have the same value. Your makeArrayfunction calls itself recursively but it doesn't do anything (even if you add a sysout statement ;) )
关于您的代码，您迭代i以填充整个数组（无论您从哪里知道大小），但您始终将值设置为根节点的值。这就是为什么你总是拥有相同的价值。您的makeArray函数以递归方式调用自身，但它不执行任何操作（即使您添加了 sysout 语句 ;)）
Update:
更新：
And for the constraint of using no lists, here is another version that uses only arrays:
对于不使用列表的限制，这是另一个仅使用数组的版本：
int size = 20;
int[] results = new int[size];
extractValues(n, results, 0);
with the method definition:
使用方法定义：
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;
}
Note, that the result will be in results, then. The size has to be either assumed to be larger the number of nodes or it has to be counted by traversing the tree, before.
请注意，结果将在results，然后。大小必须要么假设为大于节点数，要么必须通过遍历树来计算，之前。
回答by CEGRD
How about this: (Your recursion does not make any changes to the array)
怎么样：（您的递归不会对数组进行任何更改）
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);
}
}
回答by Rafael
You can traverse the tree adding the elements into an array. For example, using preOrder traversal you would have something like this:
您可以遍历树，将元素添加到数组中。例如，使用 preOrder 遍历，你会有这样的事情：
void preOrder (BSTNode root){
if(root == null)
return;
array.add(root.getValue);
preOrder(root.leftNode());
preOrder(root.rightNode());
}
