2

非常に簡単な質問:

このコンストラクターを使用する二分探索木の配列を (順番に) 再帰的に作成するにはどうすればよいですか?

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

2 に答える 2

4

In-Order とは、最初にツリーの左側の部分をトラバースする必要があることを意味するため、次のようになります。

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-17T02:36:55.030 に答える
3

ありがとう、それはうまくいきました。Javaではジェネリックの配列を作成できないため、アルゴリズムを使用してArrayListで機能させました（提案したように）他の誰かが同じ質問をする場合に備えて、（上記のコンストラクターを使用して）メソッドを次に示します。(参照は、現在のツリー ノードへの参照です)

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-17T21:48:08.840 に答える