Java 将二叉树转为有序数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16180569/
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
Turning a Binary Tree to a sorted array
提问by Adegoke A
Is there a way to turn a Binary to a sorted array without having to traverse the tree for every array index?
有没有办法将二进制转换为排序数组，而不必为每个数组索引遍历树？
Node root;
Node runner;
int current_smallest;
void findsmallest(Node root){
//Pre-order traversal
if(root == null){
return;
}else{
runner = root;
if(current_smallest == null){
current_smallest = runner.element;
}else{
if(current_smallest > runner.element){
current_smallest = runner.element;
}
}
findsmallest(runner.left);
findsmallest(runner.right);
}
}
void fill_array( int [] array ){
for(int i =0; i < array.length(); i++){
findsmallest(root);
array[i] = current_smallest;
}
}
As you can see this can be take a long time if there are a lot of nodes in the tree. Btw, I forgot to show that the whole tree would have to be traversed at the start to get the length of the array.
如您所见，如果树中有很多节点，这可能需要很长时间。顺便说一句，我忘了表明必须在开始时遍历整棵树才能获得数组的长度。
回答by Tom
A binary tree can be represented in an array; if this were the case, all you would need to do is sort the array.
二叉树可以用数组表示；如果是这种情况，您需要做的就是对数组进行排序。
Here's some more info on representing the tree in the array: wikipedia
这里有一些关于在数组中表示树的更多信息： 维基百科
This is not necessarily the most space-efficient representation; the "nodes with references" representation may waste less space.
这不一定是最节省空间的表示；“带有引用的节点”表示可能会浪费更少的空间。
回答by femtoRgon
What you want is an in-order traversal, which is generally implemented recursively like:
你想要的是一个有序遍历，它通常是递归实现的，如：
- Traverse left subtree.
- Handle this node (ie. insert as the next element in your array)
- Traverse right subtree.
- 遍历左子树。
- 处理此节点（即作为数组中的下一个元素插入）
- 遍历右子树。
回答by dasblinkenlight
Yes, you can do that: run an in-order traversalof the tree, keep the current position of the array, and store the node's value at the then-current position of the array.
是的，您可以这样做：运行树的有序遍历，保留数组的当前位置，并将节点的值存储在数组的当前位置。
You can do in-order traversal recursively, or you can do it with a stack data structure. If you want to do it recursively, you can do this:
您可以递归地进行有序遍历，也可以使用堆栈数据结构进行遍历。如果你想递归地做，你可以这样做：
int fill_array(Node root, int [] array, int pos) {
if (root.left != null) {
pos = fill_array(root.left, array, pos);
}
array[pos++] = root.element;
if (root.right != null) {
pos = fill_array(root.right, array, pos);
}
return pos; // return the last position filled in by this invocation
}
Note that in order for the above recursive procedure to work, the caller must allocate enough space in the arraypassed into the function.
请注意，为了使上述递归过程起作用，调用者必须在array传入函数中分配足够的空间。
