2

再帰的にツリーをトラバースし、その再帰メソッドにスコープされた配列を返す方法はありますか?

だから私は最近、このトピックに関する他の誰かの質問に答えました. その質問はここにあります: SO Question。私のソリューションでは、再帰の範囲外の配列を使用しているため、メソッドは配列を返すことができません (または、少なくとも返すべきではありません)。ただし、配列を返すようにツリーをトラバースするための再帰メソッドを作成する方法はありますか? 再帰的なメソッドを呼び出す初期メソッドを書いても問題ありませんが、これを行う良い方法が思いつきません。

前に提案したコードは次のとおりです。

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}

ご覧のとおり、ArrayListは再帰の範囲外です。したがって、それを返すことはあまり意味がありません。これを行うより良い方法はありますか？

4

3 に答える 3

5 
public static List traversePreRecursive(Node node) {
    if (node == null) return new ArrayList();

    List nodeValues = new ArrayList();
    nodeValues.add(node.getValue());
    nodeValues.addAll(traversePreRecursive(node.getLeft()));
    nodeValues.addAll(traversePreRecursive(node.getRight()));

    return nodeValues;
}
于 2013-06-08T05:21:30.607 に答える
2

別の方法がありますが、ツリーを 2 回通過する必要があります。私の最初の回答の配列操作があなたに悲しみを与えていた場合にのみ、この代替手段を採用するでしょう。このアプローチは、各ノード (メソッド) にインデックスを提供することから始まります。index()基本的には、実際に配列を作成する前に、ノードが配列のどの要素を占有する必要があるかを判断します。これにより、ノードの数もわかります ( size)。list次に、すべてのノードを保持するのに十分な大きさの配列 ( ) を割り当て、それをメソッド ( addToList) に渡します。このメソッドは、ノード参照を配列内の以前に識別された要素にコピーします。

public static List<Node> getNodes(Node a) {
    int size = index(a, 0);
    List<Node> list = new ArrayList<Node>(size);
    addToList(a, list);
    return list;
}

private static int index(Node node, int index) {
    if (node == null) return index;

    node.setIndex(index);
    int iLeft = index(node.getLeft(), index++);
    int iRight = index(node.getRight(), iLeft++);

    return iRight + 1;
}

private static void addToList(Node node, List<Node> list) {
    if(node == null) return;
    list.add(node.getIndex(), node);
    addToList(node.getLeft(), list);
    addToList(node.getRight(), list);
}
于 2013-06-08T15:47:06.753 に答える
0

c では、静的関数変数を使用できます (つまり、関数の 1 回の反復でリストに値を追加すると、次の反復でその値がリストに含まれることになります。リストが静的な場合)。ただし、それらを使用することはできません。あなたが提案している問題に対する最善の (最適な) 解決策です。したがって、静的変数を検索していると思いますが、これはそれらを使用する適切なケースではありません。

于 2013-06-08T05:25:47.283 に答える