二叉树定义：二叉树是每个结点最多有两个子树的树结构。

二叉树的特点：

1. 每个节点最多有两个子节点，即二叉树不存在大于2的节点；

2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

二叉树的结构：

二叉树的性质：

1. 在非空二叉树中，第 i 层的节点总数不超过 2 ^i-1，i >= 1；

2. 深度为 h 的二叉树最多有 2 ^h - 1 个节点(h>=1)，最少有 h 个节点；

3. 对于任意一棵二叉树，如果其叶节点总数为 n1，而度数为2的节点总数为 n2，则 n1 = n2+1；

4. 具有 n 个节点的完全二叉树的深度为 (Log₂n) +1；

5. 对于任意一个根节点，如果根节点的下标为n，那么它的左节点下标为 2n+1，右节点下标为 2n+2，根据这点可以很方便的用数组来保存二叉树的节点。

实现二叉树：

 1import java.util.ArrayList;
 2import java.util.List;
 3
 4class BinaryTree<E> {
 5    // 根节点
 6    private Node<E> _root;
 7    // 用列表暂时保存下节点
 8    private List<Node<E>> nodes = new ArrayList<>();
 9
10    public void createTree(E[] array) {
11        if (array.length == 0) {
12            return;
13        }
14        for (E e : array) {
15            nodes.add(new Node<>(null, null, null, e));
16        }
17        // 获取根节点
18        if (nodes.get(0) != null) {
19            _root = nodes.get(0);
20        }
21        // 根据二叉树的特性5来确定每个节点的左右子节点
22        for (int i = 0; i < nodes.size(); i++) {
23            if ((i * 2 + 1) < nodes.size() && nodes.get(i * 2 + 1) != null) {
24                nodes.get(i).left = nodes.get(i * 2 + 1);
25            }
26            if ((i * 2 + 2) < nodes.size() && nodes.get(i * 2 + 2) != null) {
27                nodes.get(i).right = nodes.get(i * 2 + 2);
28            }
29        }
30    }
31
32    // 节点类
33    static class Node<E> {
34        // 父节点暂时没有用到
35        Node<E> parent;
36        // 左节点
37        Node<E> left;
38        // 右节点
39        Node<E> right;
40        // 节点中存储的数据
41        E data;
42
43        Node(Node<E> parent, Node<E> left, Node<E> right, E data) {
44            this.data = data;
45            this.parent = parent;
46            this.left = left;
47            this.right = right;
48        }
49
50        @Override
51        public String toString() {
52            return data.toString();
53        }
54    }
55
56    public static void main(String[] args) {
57        Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8};
58        BinaryTree<Integer> binaryTree = new BinaryTree<>();
59        binaryTree.createTree(array);
60    }
61}

实现二叉树的代码很简单，主要就是通过上述的性质5来确定每一个节点的左右子节点，一层一层的绑定关系，最终就可以将所有的节点联系完整。下面是二叉树生成的整个顺序：

二叉树的遍历：

前面我们生成了一棵二叉树，虽然生成了，但是却不知道如果去遍历二叉树输出每个节点对应的数据，那就等于拿到了某件东西却不会使用，这也是不希望看到的一种情况，下面就看看如果遍历一棵二叉树吧！

1. 先序遍历： 首先访问根节点，这也就是为什么上面创建二叉树的时候要保存根节点的用处，根节点访问之后在访问其左子树，最后再访问右子树；在访问左右子树的时候依旧是按照先根然左后右的顺序。文字想必大家都看的模棱两可的，下面看顺序图吧，更直观，更清晰：

   

   

   

   

   

   
   以上就是整个先序遍历的流程，这九个步骤大家应该一眼就能看的懂，用代码更加容易实现：

 1    /**
 2     * 先序遍历，访问根节点的操作发生在遍历其左右节点之前
 3     *
 4     * @param node 某个根节点
 5     */
 6    public void preOrder(Node<E> node) {
 7        if (node == null) {
 8            return;
 9        }
10        System.out.print(node + " ");
11        preOrder(node.left);
12        preOrder(node.right);
13    }

2. 中序遍历：首先访问根节点的左子树，直到左子树访问完，回过头来访问根节点，最后访问左子树，这里便不在贴流程图了，简单的把实现代码贴出来：

 1    /**
 2     * 中序遍历，访问根节点的操作发生在遍历左右节点中间
 3     *
 4     * @param node 某个根节点
 5     */
 6    public void inOrder(Node<E> node) {
 7        if (node == null) {
 8            return;
 9        }
10        inOrder(node.left);
11        System.out.print(node + " ");
12        inOrder(node.right);
13    }

3. 后序遍历：首先访问根节点的左子树，直到左子树访问完，回到根节点的右子树，访问完，最后访问根节点，照样贴上实现代码：

 1    /**
 2     * 后序遍历，访问根节点的操作发生在遍历左右节点之后
 3     *
 4     * @param node 某个根节点
 5     */
 6    public void postOrder(Node<E> node) {
 7        if (node == null) {
 8            return;
 9        }
10        postOrder(node.left);
11        postOrder(node.right);
12        System.out.print(node + " ");
13    }

至此为止，二叉树的内容就结束了，整个的源码可以扫描下方的二维码，我会将源码奉上，切记多敲几遍，这样就才能在脑海中加深印象，不然看过觉得理解了，三天之后就又抛之脑后了！

如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！