如何用广度优先搜索解决这个问题?

Question

假定在一个树,即其根结点为A,有多个数目不定的子节点,如B C D E---.其中每个子节点又有数目不等的多个子节点,如B子节点有B1 B2 B3 B4--,C节点下有子节点C1 C2 C3 C4 C5---,以此类推.假定每个节点都包括字符串数据.假如有str1,str2,str3.要求与各层节点中的数据比较,寻找具备相应的字符串的节点,并打印其路径.
如A中如包括有str1,那么再在 B C D E--中寻找包涵 str2的节点,假定B C中存在str2,再在B C的子节点 B1 B2 B3 B4-- C1 C2 C4 C5 --查找包涵str3的子节点,假如B1 B4,C2 C4 C5中包涵str3.那么,打印出其路径
1.A B B1
2.A B B4
3.A C C2
4.A C C4
5.A C C5这个如果使用栈+递归的方法,我想我或许能够解决.但如果以广度优先+队列,怎样解决呢?一点思路都没有,请高手指点一下?

Answer 1

递归:
@param 树节点
@param Vector中存放需要匹配的串
@param sb 反向的路径串
@return 当pipei式在当前结点已经完成匹配时返回true,当子pipei式在某个子为true且当前结点匹配的话,返回true,否则返回false;
boolean match(Tree t,Vector pipei,StringBuffer sb)
{
    if(t.node.equals((String)pipei.remove(0)))
    {
        Tree [] childs=t.children();
        if(pipei.size()==0)return true;
        for(int  i=0;i<childs.length;i++)
        {
             if(print(childs[i],pipei,sb))
             {
                 sb.append(t.name);
                 return true;
              }
         }
     }
     return false;
}

Answer 2

你的树是以什么方式（数据结构 or 持久化物件 etc.）来存储的？我只是觉的按你的描述，最后比配路径会比较合适

Answer 3

看见你的短信了, 你需要自己决定确定一个数据结构. 有很多树的结构可以供你选择, 比如经典的jive里的treewalker, dp的composite, 或者longtree, 或者swing里的treemodel, 所以我上边问你, 你是以什么方式来存贮树结构的, 或者你用持久的XML, 总得先自己定个数据结构,虽然在各个结构上有效率差异, 如你的树不太深或太广,这些树结构是没有区别的. 你说出你要选择的树的结构, 然后我可以帮你参考算法.

Answer 4

看楼主顶的辛苦，呵呵，试着帮你写了个。
由于楼主没有给出具体的建树的过程，这里给出自己的一个建树的过程。
只用了一个队列。
import java.util.*;
public class Main
{ public static void main(String [] args) throws Exception
{
int n=3;
String [] str={"1","2","3"};
  Node A=new Node("1","A",null);
  Node B=new Node("2","B",A);
  Node C=new Node("2","C",A);
  new Node("3","B1",B);
  new Node("x","B2",B);
  new Node("x","B3",B);
  new Node("3","B4",B);
  new Node("x","C1",C);
  new Node("3","C2",C);
  new Node("x","C3",C);
  new Node("3","C4",C);
  new Node("3","C5",C);
 
  List<Node> queue=new LinkedList<Node>();
  if(A.value.equals(str[A.level]))
  queue.add(A);
  while(queue.size()>0)
  {
  Node cur=queue.remove(0);
  LinkedList<Node> children=cur.children;
  for(int i=0;i<children.size();i++)
  {
  if(children.get(i).value.equals(str[cur.level+1]))
  {
  if(cur.level+1==n-1)
  System.out.println(children.get(i).path);
  else
  {
  children.get(i).level=cur.level+1;
  queue.add(children.get(i));
  }
 
  }
 
  }
  }  
 
 
}
}
class Node
{
public int level=0;
public String path="";
public LinkedList<Node> children=new LinkedList<Node>();
public String value="";
public String name="";
public Node(String val,String name,Node parent)
{
this.value=val;
this.name=name;
if(parent!=null)
{
parent.addChild(this);
path=parent.path+" "+name;
}
else
path=name;
}
public void addChild(Node child)
{
children.add(child);
}}

Answer 5

"多树的结构可以供你选择, 比如经典的jive里的treewalker, dp的composite, 或者longtree, 或者swing里的treemodel, 所以我上边问你, 你是以什么方式来存贮树结构的, 或者你用持久的XML, 总得先自己定个数据结构"我不懂,怎么有这么多的树结构?谁能解释一下,各种树结构的特点?

Answer 6

谁能以XML TREEMODEL分别举例说明一下???

Answer 7

此类的题在数据结构和人工智能书里有很多讲解。一般，队列用于广度优先搜索，堆栈用于深度优先搜索。
关于路径问题，楼主可以让每个节点拥有一个自己的序号和一个父节点的序号，
class Node{}

Answer 8

不小心点错了，接着说
class Node{
  int currentIndex;
  int parentIndex;
}
找到目标节点后，沿着父节点序号向上一个一个顺藤摸瓜就可以知道路径了

Answer 9

class Node{
  int currentIndex;
  int parentIndex;
}怎么搞法？