一、二叉树的创建

1.1 二叉树创建原理

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
基本思路是：假设以一个数组为例，用数组中的元素创建二叉树，第一步，先将所有的值转变为Node节点，并依次存放如LinkedList中。
以第一个节点为头结点，循环创建左右孩子节点。根据数组的元素个数的奇偶判断最后一个节点是否有右孩子节点。
数组从0开始满足第i个结点的左孩子为2i+1,右孩子为2i+2
利用这个性质即可创建二叉树

---

1.2 二叉树创建代码实现

创建节点类BTNode

public class BTNode {
    //为了直观显示，左右孩子都设为public,不再设置get、set方法
    public BTNode leftChild;
    public BTNode rightChild;
    public int data;
    public BTNode(int data){
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
    }
}

创建二叉树方法类BTNodeUtil
方法类中实现静态方法通过数组创建二叉树并返回根节点

public class BTNodeUtil {

    public static BTNode createBTNodebyArray(int[] a) {
        //将数组中的元素转化为二叉树结点存入list中
        LinkedList<BTNode> list = new LinkedList<>();
        for (int i = 0; i < a.length; i++) {
            list.add(new BTNode(a[i]));
        }

        //根据二叉树的创建规则开始创建二叉树,注意下标从零开始
        for (int parentIndex = 0; parentIndex < list.size() / 2 - 1; parentIndex++) {
            list.get(parentIndex).leftChild = list.get(parentIndex * 2 + 1);
            list.get(parentIndex).rightChild = list.get(parentIndex * 2 + 2);
        }

        //最后一个父节点单独拿出来处理,因为可能没有右孩子
        int lastParentIndex = list.size()/2 - 1;
        list.get(lastParentIndex).leftChild = list.get(lastParentIndex * 2 + 1);

        //如果元素个数为奇数，则表明最后一个结点存在右孩子结点
        if(list.size() % 2 == 1){
            list.get(lastParentIndex).rightChild = list.get(lastParentIndex * 2 + 2);
        }

        //返回根节点
        return list.get(0);
    }
}

下面介绍完递归遍历之后将会给出测试数据

---

二、二叉树的遍历

我们知道二叉树的遍历分为前序遍历、中序遍历和后序遍历。而每一种遍历方式又可以通过递归和非递归实现。这里先介绍递归实现
代码原理很简单，这里不做叙述
实现代码如下：

public class Order {

    //前序递归遍历
    public static void preOrder(BTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    //中序递归遍历
    public static void inOrder(BTNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.data + " ");
            inOrder(node.rightChild);
        }
    }

    //后序递归遍历
    public static void postOrder(BTNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.data + " ");
        }
    }
}   

---

三、测试代码

下面部分是测试代码

   /**
     * 构建二叉树
     *           3
     *       2      4
     *     5   2   2  4
     *   5
     * @param args
     */
    public static void main(String[] args) {
        int[] a = {3,2,4,5,2,2,4,5};
        BTNode root = BTNodeUtil.createBTNodebyArray(a);
        System.out.print("先序遍历为：");
        preOrder(root);
        System.out.println();
        System.out.print("中序遍历为：");
        inOrder(root);
        System.out.println();
        System.out.print("后序遍历为：");
        postOrder(root);
    }

输出结果为：

先序遍历为：3 2 5 5 2 4 2 4 
中序遍历为：5 5 2 2 3 2 4 4 
后序遍历为：5 5 2 2 2 4 4 3