二叉树构建和遍历

import java.util.ArrayList;
import java.util.Stack;


public class BinaryTree {


    public static void main(String[] args) {
        /*
         *                  0
         *                 /  \
         *               1     2
         *              /  \   /\
         *             3    4 5  6
         */
        int[] arr = new int[]{
                0, 1, 2, 3, 4, 5, 6
        };


        TreeNode root = createBinaryTree(arr, 0);
        getDFS(root);
        getBFS(root);


    }


    private static int getDeep(int index) {
        int deep = 1;
        while (index > 0) {
            deep += 1;
            index = (index-1)/2;
        }


        return deep;
    }


    //构建二叉树
    private static TreeNode createBinaryTree(int[] arr, int index) {
        TreeNode node = null;
        if (index < arr.length) {
            int value = arr[index];
            node = new TreeNode(value, getDeep(index));
            node.left = createBinaryTree(arr, index * 2 + 1);
            node.right = createBinaryTree(arr, index * 2 + 2);
            return node;
        }
        return node;
    }


    //深度优先遍历-先序遍历
    private static void getDFS(TreeNode root) {
        System.out.println("深度优先遍历-先序遍历：");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);


        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            for (int i=0; i<temp.deep; i++) {
                System.out.print("\t");
            }
            System.out.println(temp.value);
            //这里利用了堆的--先进后出的特性，所以右节点要在左节点前入堆
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }


    }


    //广度优先遍历-先序遍历
    private static void getBFS(TreeNode root) {
        System.out.println("广度优先遍历-先序遍历：");
        if (root == null) {
            return;
        }
        ArrayList<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        while (queue.size() > 0) {
            TreeNode temp = queue.remove(0);
            for (int i=0; i<temp.deep; i++) {
                System.out.print("\t");
            }
            System.out.println(temp.value);
            //这里利用了队列的--先进先出的特性，所以左节点要在右节点前入堆
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }


    //二叉树结构
    static class TreeNode {
        int value;
        int deep;
        TreeNode left;
        TreeNode right;


        TreeNode(int value, int deep) {
            this.value = value;
            this.deep = deep;
        }
    }


}