0

我目前正在尝试为整数元组实现 trie 数据结构。并实施如下：

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

}

然后我有一个 trie 类，如下所示：

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

我可以向这个 trie 添加值，但我需要能够迭代这个并且想知道我怎么能做到这一点？例如，如果我想使用迭代器打印树......任何帮助都会很棒......

4

1 回答 1

0

交互器只需要实现Iterator接口，只需要提供boolean hasNext()和Integer next(). 所以要问的问题是：如何在你的 trie 中表示一个位置，以便（a）获取与该位置关联的值，以及（b）在给定当前位置的情况下找出“下一个”位置？

我将避免发布实际的解决方案，因为我不确定这是否是家庭作业。但是请考虑：您可以通过选择特定的 trie 节点以及您用来到达它的 trie 节点的路径来表示您的 trie 中的“当前位置”。然后你可以递归地计算“下一个”元素：如果当前元素是一个有子节点的节点，那么找到第一个子endOfTuple节点true。如果当前元素没有子元素，则转到其父元素并前进到该父元素的下一个子元素。如果那个父母没有下一个孩子，那就去它父母的下一个孩子，等等。

于 2013-03-23T16:35:51.133 回答