二叉搜索树，以序阵列

递归我怎么可以创建一个二叉搜索树（按顺序）的阵列使用这种构造：

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; 
    }

来源

2013-04-17 Greg

在订单意味着你首先要遍历树的左侧部分，所以：

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

的方法本身可能看起来是这样的：

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 
}

有点像这样。我只是不确定索引和它需要增加的地方。如果您不想担心索引，或者您不知道树中有多少个节点，则可以使用ArrayList，最后将其转换为数组。

通常清洁呼叫的方法是建立一个围绕这样的递归方法：

public E[] inOrderSort(TreeNode tree){ 
    E[] array = new E[tree.size]; 
    inOrder(tree, array, 0); 
    return array; 
}

来源

2013-04-17 02:36:55 GameDroids

谢谢，这真是棒极了。 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); 
}

来源

2013-04-17 21:48:08 Greg

二叉搜索树，以序阵列

回答

相关问题