树的广度和深度遍历

  1 package alibaba;
  2 /**
  3  * 深度优先遍历--->栈；
  4           广度优先遍历--->队列； 
  5  */
  6   import java.util.ArrayDeque;  
  7       
  8     public class BinaryTree {  
  9         static class TreeNode{  
 10             int value;  
 11             TreeNode left;  
 12             TreeNode right;  
 13               
 14             public TreeNode(int value){  
 15                 this.value=value;  
 16             }  
 17         }  
 18           
 19         TreeNode root;  
 20           
 21         public BinaryTree(int[] array){  
 22             root=makeBinaryTreeByArray(array,1);  
 23         }  
 24       
 25         /** 
 26          * 采用递归的方式创建一颗二叉树 
 27          * 传入的是二叉树的数组表示法 
 28          * 构造后是二叉树的二叉链表表示法 
 29          */  
 30         public static TreeNode makeBinaryTreeByArray(int[] array,int index){  
 31             if(index<array.length){  
 32                 int value=array[index];  
 33                 if(value!=0){  
 34                     TreeNode t=new TreeNode(value);  
 35                     array[index]=0;  
 36                     t.left=makeBinaryTreeByArray(array,index*2);  
 37                     t.right=makeBinaryTreeByArray(array,index*2+1);  
 38                     return t;  
 39                 }  
 40             }  
 41             return null;  
 42         }  
 43           
 44         /** 
 45          * 深度优先遍历，相当于先根遍历 
 46          * 采用非递归实现 
 47          * 需要辅助数据结构：栈 
 48          */  
 49         public void depthOrderTraversal(){  
 50             if(root==null){  
 51                 System.out.println("empty tree");  
 52                 return;  
 53             }         
 54             ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();  
 55             stack.push(root);         
 56             while(stack.isEmpty()==false){  
 57                 TreeNode node=stack.pop();  
 58                 System.out.print(node.value+"    ");  
 59                 if(node.right!=null){  
 60                     stack.push(node.right);  
 61                 }  
 62                 if(node.left!=null){  
 63                     stack.push(node.left);  
 64                 }             
 65             }  
 66             System.out.print("
");  
 67         }  
 68       
 69         /** 
 70          * 广度优先遍历 
 71          * 采用非递归实现 
 72          * 需要辅助数据结构：队列 
 73          */  
 74         public void levelOrderTraversal(){  
 75             if(root==null){  
 76                 System.out.println("empty tree");  
 77                 return;  
 78             }  
 79             ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();  
 80             queue.add(root);  
 81             while(queue.isEmpty()==false){  
 82                 TreeNode node=queue.remove();  
 83                 System.out.print(node.value+"    ");  
 84                 if(node.left!=null){  
 85                     queue.add(node.left);  
 86                 }  
 87                 if(node.right!=null){  
 88                     queue.add(node.right);  
 89                 }  
 90             }  
 91             System.out.print("
");  
 92         }  
 93           
 94         /**  
 95          *                  13 
 96          *                 /   
 97          *               65    5 
 98          *              /       
 99          *             97  25   37 
100          *            /    /   / 
101          *           22   4 28 32 
102          */  
103         public static void main(String[] args) {  
104             int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};  
105             BinaryTree tree=new BinaryTree(arr);  
106             tree.depthOrderTraversal();  
107             tree.levelOrderTraversal();  
108         }  
109     }