Java 二叉树，深度优先遍历，广度优先遍历

 二叉树的深度优先遍历，可以使用栈，因为栈有后进先出的特性，

二叉树的广度优先遍历，可以使用队列来实现。

package sjjg;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Tree1 {

    public static void main(String[] args) {

        int[] arr = {1,2,3,4,5,6,7};

        TreeNode root = createBinaryTree(arr, 0);

        getDFS(root);
        System.out.println();
        getBFS(root);

    }


    /**
     * 将一个数组，转为二叉树
     * 就是0 个为根，1个为根的左子树，2个为根的右子树，以此类推
     * 发现规律，对于二叉树，一个节点的左子树为index*2+1
     * 右子树为index*2+2
     */
    public static TreeNode createBinaryTree(int[] arr, int index){
        TreeNode node = null;
        if (index<arr.length){
            int value = arr[index];
            node = new TreeNode(value);
            node.left = createBinaryTree(arr,index*2+1);
            node.right = createBinaryTree(arr,index*2+2);
            return node;
        }
        return node;
    }

    /**
     * 深度优先遍历
     */
    public static void getDFS(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = null;
        while (!stack.isEmpty()){
            temp = stack.pop();
            System.out.print(temp.value+"\t");
            // 因为栈是先进后出的，所以先进右
            if (temp.right != null)
                stack.push(temp.right);
            if (temp.left != null)
                stack.push(temp.left);
        }
    }

    /**
     * 广度优先遍历
     */
    public static void getBFS(TreeNode root){
        if (root == null) return;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        TreeNode temp = null;
        while (!queue.isEmpty()){
            temp = queue.remove();
            System.out.print(temp.value+"\t");
            if (temp.left != null)
                queue.add(temp.left);
            if (temp.right != null)
                queue.add(temp.right);
        }
    }

    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value) {
            this.value = value;
        }
    }

}