Trie数据结构中的遍历和打印键算法

Question

我正在处理一个处理Trie数据结构实现的项目。其中一种必需的方法是按dfs顺序打印Trie的所有密钥。每个节点都有一个布尔变量，表示它是否是一个终端节点，它的引用存储在一个大小为10的数组中。假设分支的一部分是3456（3-> 4-> 5-> 6），并且5和6是终端节点，并且6是分支的最后一个节点 - >即打印键时，我只需要打印此分支的345和3456。但事情是我不知道如何使用递归做到这一点...任何想法？

顺便说一下，这些关键数字不需要作为变量存储在每个节点中，只需通过数组中对应的索引来引用它们（例如：3表示节点存储在children [3]中）

Answer 1

尝试是这样的：但是

private Node Find(Node x, String key, int d) 
{ // Return value associated with key in the subtrie rooted at x. 
    if (x == null) 
     return null; 

    if (d == key.Length) 
    { 
     return x; 
    } 

    char c = key[d]; // Use dth key char to identify subtrie. 

    return Find(x.Children[c], key, d + 1); 
} 

public IEnumerable<String> GetAllKeys() 
{ 
    Queue<String> q = new Queue<String>(); 
    Collect(Find(Root, "", 0), "", q); 
    return q; 
} 

private void Collect(Node x, String pre, Queue<String> q) 
{ 
    if (x == null) return; 
    if (x.NullNode) q.Enqueue(pre); 
    for (int c = 0; c < 256; c++) 
     Collect(x.Children[c], pre + ((char)c), q); 
} 

您可能必须调整它一点点为您实现。