时间戳

首页 > 解决方案 > Java 中 Trie 上的 DFS 和 BFS

java - Java 中 Trie 上的 DFS 和 BFS

问题描述

我有一个看起来像这样的 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

我不知道出了什么问题。

标签： javatreetrie

解决方案

我已经实现了我在评论中提到的基于地图的方法，即不修改原始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

推荐阅读