java 二叉搜索树排序数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16050219/
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
Binary Search Tree to inOrder Array
提问by Greg
Pretty easy question:
很简单的问题：
Recursively how can I create an array of a binary search tree (in order) which uses this constructor:
递归地如何创建使用此构造函数的二叉搜索树数组（按顺序）：
public class OrderedSet<E extends Comparable<E>> {
private class TreeNode {
private E data;
private TreeNode left, right;
public TreeNode(E el) {
data = el;
left = null;
right = null;
}
}
private TreeNode root;
public int size = 0;
public OrderedSet() {
root = null;
}
回答by GameDroids
In-Order means you first have to traverse the left part of the tree, so:
有序意味着您首先必须遍历树的左侧部分，因此：
TreeNode tree // this is your tree you want to traverse
E[] array = new E[tree.size]; // the arrays length must be equivalent to the number of Nodes in the tree
int index = 0; // when adding something to the array we need an index
inOrder(tree, array, index); // thats the call for the method you'll create
The method itself could looks something like this:
该方法本身可能如下所示：
public void inOrder(TreeNode node, E[] array, int index){
if(node == null){ // recursion anchor: when the node is null an empty leaf was reached (doesn't matter if it is left or right, just end the method call
return;
}
inOrder(node.getLeft(), array, index); // first do every left child tree
array[index++]= node.getData(); // then write the data in the array
inOrder(node.getRight(), array, index); // do the same with the right child
}
Somewhat like that. I am just not sure about the index and where it needs to be incremented. If you don't want to worry about the index or if you don't know how many nodes are in the tree, then use an ArrayList instead and transform it in the end to an array.
有点像。我只是不确定索引以及它需要增加的位置。如果您不想担心索引，或者您不知道树中有多少个节点，那么请改用 ArrayList 并将其最后转换为数组。
Normally a cleaner call method is build around the recursive method like this:
通常，一个更清晰的调用方法是围绕递归方法构建的，如下所示：
public E[] inOrderSort(TreeNode tree){
E[] array = new E[tree.size];
inOrder(tree, array, 0);
return array;
}
回答by Greg
Thanks, that worked great. Java wouldn't allow me to make an array of generics so using your algorithm I made it work with an ArrayList (like you suggested) Here's the method (using the above constructor) just incase someone else asks the same question. (Ref is my reference to the current tree node)
谢谢，效果很好。Java不允许我创建一个泛型数组，所以使用你的算法我让它与一个ArrayList一起工作（就像你建议的那样）这是方法（使用上面的构造函数）以防其他人问同样的问题。（Ref 是我对当前树节点的引用）
public ArrayList<E> toArray() {
ArrayList<E> result = new ArrayList<E>();
toArrayHelp(root, result);
return result;
}
private void toArrayHelp(TreeNode ref, ArrayList<E> result) {
if (ref == null) {
return;
}
toArrayHelp(ref.left, result);
result.add(ref.data);
toArrayHelp(ref.right, result);
}
