1

我在java中有一个完全构建的通用Trie。我试图遍历 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]

并且所有这些数组/列表都可以在一个最后返回的 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 回答