DFS和BFS在Java中的Trie

Question

我有一个Trie，看起来像这样：

Root
/    
b      c
/      / 
a      a   h
/      /   / 
t      t   a   e
/   /
t   e
/ 
r   s
/     
s       e

我正在尝试实施DFS和BFS。BFS 使用队列工作正常：

public String breadthFirstSearch() {
//FIFO Queue to hold nodes
Queue<TrieNode> nodeQueue = new LinkedList<TrieNode>();
//Output array
ArrayList<Integer> out = new ArrayList<Integer>();
//Start from root
nodeQueue.add(this.root);
//While queue is not empty
while (nodeQueue.isEmpty() == false) {
//Remove and return first queue element
TrieNode current = nodeQueue.poll();
//For node's children
for (int i=0; i<26; i++) {
//If not null
if (current.offspring[i] != null) {
//Add node to queue
nodeQueue.add(current.offspring[i]);
//Add node's index (char) to output array
out.add(i);                    
}
}
}
//Return result
return indexArrayToString(out);
}

输出：

b,c,a,a,h,t,t,a,e,t,e,r,s,s,e

现在，我正在尝试实现DFS(相同的算法，但使用堆栈(，但是输出不正确：

public String depthFirstSearch() {
//LIFO Stack to hold nodes
Stack<TrieNode> nodeStack = new Stack<TrieNode>();
//Output array
ArrayList<Integer> out = new ArrayList<Integer>();
//Start from root
nodeStack.push(this.root);
//While stack is not empty
while (nodeStack.isEmpty() == false) {
//Remove and return first stack element
TrieNode current = nodeStack.pop();
//For node's children
for (int i=0; i<26; i++) {
//If not null
if (current.offspring[i] != null) {
//Add node to stack
nodeStack.push(current.offspring[i]);
//Add node's index (char) to output array
out.add(i);                    
}
}
}
//Return result
return indexArrayToString(out);
}

这给出了：

b,c,a,h,a,e,e,r,s,e,s,t,t,a,t

当我希望它给出：

t,a,b,t,a,t,a,s,r,e,s,e,e,h,c

我不知道出了什么问题。

Answer 1

我已经实现了我在评论中提到的基于映射的方法，即不修改原始TrieNode类：

public String depthFirstSearch() {
//LIFO Stack to hold nodes
Stack<TrieNode> nodeStack = new Stack<TrieNode>();
//keep set of processed nodes (processed node is a node whose children were already pushed into the stack)
Set<TrieNode> processed = new HashSet<TrieNode>();
//boolean for checking presence of at least one child
boolean hasChild=false;
//map for trienode->char
Map<TrieNode, Integer> map = new HashMap<TrieNode, Integer>();
//Output array
List<Integer> out = new ArrayList<Integer>();
//Start from root
nodeStack.push(this.root);
//While stack is not empty
while (nodeStack.isEmpty() == false) {
//Peek at the top of stack
TrieNode topNode = nodeStack.peek();
//if it is not processed AND if it has at least one child, push its children into the stack from right to left. otherwise pop the stack
hasChild=false;                
if(!processed.contains(topNode))
{
for (int i=25; i>=0; i--) 
{
//If not null
if (topNode.offspring[i] != null) 
{
//Add node to stack and map
nodeStack.push(topNode.offspring[i]);
map.put(topNode.offspring[i], i);
hasChild=true;                                               
}     
}//end for
processed.add(topNode); //after discovering all children, put the top into set of processed nodes
if(!hasChild) //top node has no children so we pop it and put into the list
{
TrieNode popNode = nodeStack.pop();
if(map.get(popNode)!=null)
out.add(map.get(popNode)); 
}
}
else //the node has been processed already so we pop it and put into the list
{               
TrieNode popNode = nodeStack.pop();
if(map.get(popNode)!=null)
out.add(map.get(popNode)); 
}

}//end while stack not empty
//Return result
return indexArrayToString(out);
}//end method

Answer 2

若要获取所需的输出，需要考虑何时将节点添加到 out 列表中。在你的代码中，你从根开始，以一种递归风格迭代它的后代，同时将它们直接添加到你的输出中。因此，您的输出与 BFS 比 DFS 有更多的共同点。

虽然有非常简单的DFS实现，如

DFS(TrieNode current){ 
for(int i = 26; i >= 0; i--){
if(current.offspring[i] != null){
DFS(current.offspring[i]);
}
}
out.add(current);
}

如果您出于任何原因想要保留大部分代码，您可以创建第二个堆栈来跟踪您在树中的位置以及何时应该将哪个节点添加到输出中。 明确地说，这可能看起来像这样：

public String depthFirstSearch() {
//LIFO Stack to hold nodes
Stack<TrieNode> nodeStack = new Stack<TrieNode>();
//Second stack that keeps track of visited nodes
Stack<TrieNode> helpStack = new Stack<TrieNode>();
//Output array
ArrayList<Integer> out = new ArrayList<Integer>();
//Start from root
nodeStack.push(this.root);
//While stack is not empty
while (nodeStack.isEmpty() == false) {
//Remove and return first stack element
TrieNode current = nodeStack.peek();
//We visited this node -> push it on the second stack
helpStack.push(current);
//We want to add nodes to the output once we reach a leaf node, so we need a
//helper variable
boolean hasOffspring = false;
//For node's children - since we want to go the left path first we push the 
//children in right-to-left fashion on the stack. Can vary with implementation.
for (int i=25; i>=0; i--) {
//If not null
if (current.offspring[i] != null) {
//Add node to stack
nodeStack.push(current.offspring[i]);
//not a leaf
hasOffspring = true;                  
}
}
//if we reached a leaf node add it and all previous nodes to the output until 
//we reach a fork where we didn't already fo the other path
if(!hasOffspring){
TrieNode node1 = nodeStack.peek();
TrieNode node2 = helpStack.peek();
while(node1.equals(node2)){
nodeStack.pop();
helpStack.pop();
//Add node's index (char) to output array
out.add(node1);  
//we are back at the root and completed the DFS
if(nodeStack.isEmpty() || helpStack.isEmpty()) break;
node1 = nodeStack.peek();
node2 = nodeStack.peek();
}
}
}
//Return result
return indexArrayToString(out);
}