一个用于实现初始化指定个数的完全二叉树，以及两个非递归的深度优先遍历，和广度优先遍历

  1. package fifth; 
  2.  
  3. import java.util.Random; 
  4.  
  5. public class Tool{ 
  6.     public static Random rand= new Random(); 
  7. } 
  8.  
  9. ------------------------------------------------------------- 
  10.  
  11. package fifth; 
  12.  
  13. import java.util.EmptyStackException; 
  14. import java.util.LinkedList; 
  15. import java.util.Queue; 
  16. import java.util.Stack; 
  17.  
  18.  
  19. public class Tree { 
  20.     //用来实现非递归的广度优先查询与构造需要的队列 
  21.     public static Queue que= new LinkedList(); 
  22.     //用来实现深度优先查询需要的栈 
  23.     public static Stack stack=new Stack(); 
  24.     //存储的节点信息 
  25.     public int data;                                     
  26.     public Tree leftNode=null; 
  27.     public Tree rightNode=null; 
  28.      
  29.     //用来实现遍历的临时节点 
  30.     public Tree cTree=null; 
  31.      
  32.      
  33.     public Tree() { 
  34.         data=Tool.rand.nextInt(200); 
  35.         display(); 
  36.     } 
  37.      
  38.     public void display(){ 
  39.         System.out.print(data+","); 
  40.     } 
  41.      
  42.     /** 
  43.      * 创建一个以这个节点为定点的完全二叉树 
  44.      * 这个中初始化方法类似于广度优先遍历 
  45.      * @param count 要创建的完全二叉树的节点个数 
  46.      */ 
  47.     public void initTree(int count){ 
  48.         que.add(this); 
  49.         while((cTree=que.poll())!=null) 
  50.         { 
  51.             //当树中需要创建节点数小于两个时,那么就应该创造完叶子节点然后返回 
  52.             //当树中需要创建节点个数大于两个时，那么就应该把创造的子节点放入队列中，等待创建它的子节点 
  53.             if(count-2>0) 
  54.             { 
  55.                  
  56.                 cTree.leftNode=new Tree(); 
  57.                 que.add(cTree.leftNode); 
  58.                 count--; 
  59.                 cTree.rightNode=new Tree(); 
  60.                 que.add(cTree.rightNode); 
  61.                 count--; 
  62.             } 
  63.             else if(count==0) 
  64.             { 
  65.                 break; 
  66.             } 
  67.             else if(count==1) 
  68.             { 
  69.                 cTree.leftNode=new Tree(); 
  70.                 count--; 
  71.                 break; 
  72.             } 
  73.             else 
  74.             { 
  75.                 cTree.leftNode=new Tree(); 
  76.                 cTree.rightNode=new Tree(); 
  77.                 count-=2; 
  78.             } 
  79.                  
  80.         } 
  81.     } 
  82.     /** 
  83.      * 非递归的广度优先遍历,用的队列来实现 
  84.      */ 
  85.     public void breadthSearch(){ 
  86.         System.out.print('
'+"非递归广度优先遍历:"); 
  87.         //清空队列，同时把自己放在队列的第一个元素 
  88.         que.clear();que.add(this); 
  89.         while((cTree=que.poll())!=null) 
  90.         { 
  91.             //访问队列中的数据 
  92.             cTree.display(); 
  93.             if(cTree.leftNode!=null) 
  94.             { 
  95.                 que.add(cTree.leftNode); 
  96.             } 
  97.             if(cTree.rightNode!=null) 
  98.             { 
  99.                 que.add(cTree.rightNode); 
  100.             } 
  101.         } 
  102.          
  103.     } 
  104.      
  105.     /** 
  106.      * 用于栈来实现的非递归深度优先遍历 前序遍历 
  107.      */ 
  108.     public void deepFirstSearch(){ 
  109.         System.out.print('
'+"非递归深度优先遍历,前序遍历:"); 
  110.         //首先把自己压入栈底 
  111.         this.display(); 
  112.         cTree=this; 
  113.         while(cTree!=null) 
  114.         { 
  115.             if(cTree.leftNode!=null) 
  116.             { 
  117.                 stack.add(cTree); 
  118.                 cTree.leftNode.display(); 
  119.                 cTree=cTree.leftNode; 
  120.             } 
  121.             else 
  122.             { 
  123.                 while(cTree.rightNode==null) 
  124.                 { 
  125.                     try 
  126.                     { 
  127.                         cTree=stack.pop(); 
  128.                     } 
  129.                     catch(EmptyStackException e) 
  130.                     { 
  131.                         return; 
  132.                     } 
  133.                      
  134.                 } 
  135.                 cTree.rightNode.display(); 
  136.                 cTree=cTree.rightNode; 
  137.             } 
  138.         } 
  139.          
  140.     } 
  141.  
  142.     public static void main(String[] args) { 
  143.         Tree tree= new Tree(); 
  144.         tree.initTree(10); 
  145.         System.out.println(); 
  146.         tree.leftNode.display(); 
  147.         tree.rightNode.display(); 
  148.         tree.breadthSearch(); 
  149.         tree.deepFirstSearch(); 
  150.     } 
  151. }