树的宽度优先算法,怎么写...

Question

up

Answer 1

先确定一下，树有先根遍历、中根遍历和后根遍历，最后还有一个层序遍历，你说的宽度优先实际上是应该是层序遍历，就是从根开始，一层一层往下遍历。这两天写过一个二叉树的层序遍历，需要两个队列的辅助，一个用于存储遍历的中间节点，另一个存储结果节点public Iterator iteratorLevelOrder() {
// 树的层序遍历
LinkedQueue temp = new LinkedQueue(); //存储中间节点
LinkedQueue queue = new LinkedQueue();//存储结果节点

if(!isEmpty()){
temp.enQueue(root);//先把根节点放入队列
while(!temp.isEmpty()){
BinaryTreeNode node= (BinaryTreeNode)temp.deQueue();
if(node.left != null)
temp.enQueue(node.left);
if(node.right !=null)
temp.enQueue(node.right);
queue.enQueue(node.element);
}
}

return queue.iterator();//返回结果的迭代器
}

Answer 2

别人写的，你可以参考下 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 3

广度优先，随手写的。思路就是楼上说的那样
                TreeNodeCollection nodes = new TreeNodeCollection();
                
                nodes.Add(root);                for (int i = 0; i < nodes.Count; i++)
                {
                    TreeNode node = nodes[i];                    MessageBox.Show("遍历了节点：" + node.Text);                    foreach (TreeNode c in node.Nodes)
                        nodes.Add(c.Clone() as TreeNode);
                }