二叉搜索樹，以序陣列

遞歸我怎麼可以創建一個二叉搜索樹（按順序）的陣列使用這種構造：

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

二叉搜索樹，以序陣列

回答

相關問題