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