1

Javaで完全に構築された汎用Trieがあります。トライをトラバースして、各パスの完全な組み合わせをすべて取得しようとしています。たとえば、Trie に文字が含まれている場合、すべての単語の組み合わせが返されます。私の目的のために、各組み合わせのすべてのノードを配列に入れて返そうとしています。しかし、私は困惑しています。親/開始ノードに戻る前に、各子 (+ サブ子) を通過するトラバーサルのみを思いつきました (BST トラバーサルによく似ています)。ArrayList各ノードの子を保持するためにを使用しています。少し混乱している場合は申し訳ありません。コード サンプルまたは疑似コードを提供していただければ幸いです。ありがとう。

編集

組み合わせとは、次のことを意味します。Trie<char>次のような があったとします。

        "null"
       /  |   \
      a   i    t
     /   /|\    \
    t   f m n    o

返してほしい組み合わせは次のとおりです。

[a, t]
[i, f]
[i, m]
[i, n]
[t, o]

これらすべての配列/リストは、最後に返される 1 つの ArrayList に含めることができます。

4

1 に答える 1

2

(少なくとも) ツリー内のすべての文字を取得するために再帰的な方法を実行します。chars空のリストとして初期化することを確認してください

Stack startRead(Tree tree) {
  // validation check
  if (tree == null || !tree.hasChild()) return null;

  // create Stack to store the lists
  Stack listStack = new Stack();

  // for every child
  List children = tree.getChildren();
  for (Tree child : children) {
    // create a list
    List childList = new ArrayList();

    // store (push) it into stack
    listStack.push(childList);

    // call the recursive
    readIt(child, listStack);
  }

  return listStack;
}

void readIt(Tree tree, Stack listStack) {
  // pick the top list from stack
  List current = (List) listStack.pop();

  // this is the base; if tree has no child don't call this method again.
  if (!tree.hasChild()) {
    // if it's leaf add the value to current list
    current.add(tree.getValue());

    // push it back to stack
    listStack.push(current);
  } else {
    // for every child
    List children = tree.getChildren();
    for (Tree child : children) {
      // IMPORTANT! clone the list (if this fails, clone it yourself)
      // clone is called when the tree is branching
      List childList = current.clone();

      // insert this tree value to list
      childList.add(tree.getValue());

      // push it back
      listStack.push(childList);

      // call again
      readIt(child, listStack);
    }
  }
}

これにより、各組み合わせの値のリストで構成されるスタックの戻り値が得られます。

お役に立てれば。:)

于 2012-10-29T06:58:06.143 に答える