树的深度优先和广度优先

1.深度优先算法----采用栈(非递归)

/**
         * 深度优先遍历，相当于先根遍历
         * 采用非递归实现
         * 需要辅助数据结构：栈
         */
        public void depthOrderTraversal(){
            if(root==null){
                System.out.println("empty tree");
                return;
            }       
            Stack<TreeNode> stack = new Stack();   //也可以用栈实现
            stack.push(root);       
            while(stack.isEmpty()==false){
                TreeNode node=stack.pop();
                System.out.print(node.value+"    ");
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }           
            }
            System.out.print("\n");
        }

深度优先—递归

 private void depthTraversal(TreeNode tn)  
    {  
        if (tn!=null&&!tn.equals(null))   
        {  
            System.out.print(tn.value+"  ");  
            depthTraversal(tn.left);  
            depthTraversal(tn.right);  
        }         
    }

2.广度优先算法—采用队列

/**
         * 广度优先遍历
         * 采用非递归实现
         * 需要辅助数据结构：队列
         */
        public void levelOrderTraversal(){
            if(root==null){
                System.out.println("empty tree");
                return;
            }
            ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
            queue.add(root);
            while(queue.isEmpty()==false){
                TreeNode node=queue.remove();
                System.out.print(node.value+"    ");
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            System.out.print("\n");
        }