0

現在、整数タプルのトライ データ構造を実装しようとしています。そして、次のように実装しました。

import java.util.ArrayList;

public class TrieNode {

int num;
ArrayList<TrieNode> links;
boolean endOfTuple;

public TrieNode(int num)
{
    this.num = num;
    links = new ArrayList<TrieNode>();
    this.endOfTuple = false;
}

}

次に、次のようにトライクラスを作成します。

public class Trie {

TrieNode root;

public Trie() {
    root = new TrieNode(-1);
}
public void insertTuple(int[] tuple)
{
    int l = tuple.length;


    TrieNode curNode = root;

    for (int i = 0; i < l; i++)
    {
        TrieNode node = new TrieNode(tuple[i]);

        if(!curNode.links.contains(node)){
            curNode.links.add(node);
        }
        curNode = curNode.links.get(curNode.links.indexOf(node));
    }
    curNode.endOfTuple = true;  
}
}

このトライに値を追加することはできますが、これを反復できるようにする必要があり、どうすればこれを行うことができるのか疑問に思っていましたか? たとえば、イテレータを使用してツリーを印刷したい場合...どんな助けも素晴らしいでしょう...

4

1 に答える 1

0

インターレーターに必要なのは、Iteratorインターフェースを実装することだけです。したがって、質問する必要があるのは、(a) その位置に関連付けられた値をフェッチし、(b) 現在の位置から「次の」位置を割り出すことができるように、どのようにしてトライの位置を表すかということです。boolean hasNext()Integer next()

これが宿題かどうかわからないので、実際の解決策を投稿することは控えます。ただし、考慮してください。特定のトライ ノードと、それに到達するために使用したトライ ノードのパスを選択するだけで、トライの「現在位置」を表すことができます。次に、「次の」要素を再帰的に計算できます。現在の要素が子を持つノードである場合は、最初の子を見つけendOfTupleますtrue。現在の要素に子がない場合は、その親に移動し、その親の次の子に進みます。その親に次の子がいない場合は、その親の次の子に移動します。

于 2013-03-23T16:35:51.133 に答える