二叉树（BinaryTree）

定义

简单定义：由父节点与子节点组成，每个父节点最多拥有两个子节点分别称为左孩子和右孩子，第一个父节点称为根节点。
二叉树非常简单，定义上没有别的限制，但可以根据一些额外的限制条件，定义出更多的二叉树种类：

• 满二叉树：所有节点要么有0个子节点要么有两个子节点

  
  
  满二叉树.png

• 完全二叉树：除了最外层以外，每一层节点都是满的，最外层的节点都向左靠拢

  
  
  完全二叉树.png

二叉树遍历方法

二叉树可以按照三种顺序进行遍历，分别为前序遍历，中序遍历，后序遍历。如何为理解这三种遍历呢，其实只需要看父节点遍历所在位置，左右子节点顺序固定为左先右后，父节点在前面即父>左>右为前序遍历，父节点在中间即左>父>右为中序遍历，父节点在最后即左>右>父为后序遍历。遍历实现方法也很多，有递归和栈，这里介绍一种递归的实现方法。

public class BinaryTree<T> {
    public T val;
    public BinaryTree<T> left;
    public BinaryTree<T> right;

    public BinaryTree() {
    }

    public BinaryTree(T val, BinaryTree<T> left, BinaryTree<T> right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 中序遍历
     *
     * @param root
     * @param queue
     * @param <T>
     */
    public static <T> void inOrderTraversal(BinaryTree<T> root, Queue<T> queue) {
        if (root.left != null) {
            inOrderTraversal(root.left, queue);
        }
        queue.add(root.val);
        if (root.right != null) {
            inOrderTraversal(root.right, queue);
        }
        System.out.println("inOrderTraversal: " + queue);
    }

    /**
     * 前序遍历
     *
     * @param root
     * @param queue
     * @param <T>
     */
    public static <T> void preOrderTraversal(BinaryTree<T> root, Queue<T> queue) {
        queue.add(root.val);
        if (root.left != null) {
            preOrderTraversal(root.left, queue);
        }
        if (root.right != null) {
            preOrderTraversal(root.right, queue);
        }
        System.out.println("preOrderTraversal: " + queue);
    }

    /**
     * 后序遍历
     *
     * @param root
     * @param queue
     * @param <T>
     */
    public static <T> void postOrderTraversal(BinaryTree<T> root, Queue<T> queue) {
        if (root.left != null) {
            postOrderTraversal(root.left, queue);
        }
        if (root.right != null) {
            postOrderTraversal(root.right, queue);
        }
        queue.add(root.val);
        System.out.println("postOrderTraversal: " + queue);
    }

    public static void main(String[] args) {
        BinaryTree<Integer> foo = new BinaryTree<>(2, new BinaryTree<>(), new BinaryTree<>());
        foo.left.val = 1;
        foo.right.val = 3;
        BinaryTree.inOrderTraversal(foo, new ArrayDeque<>());
        BinaryTree.preOrderTraversal(foo, new ArrayDeque<>());
        BinaryTree.postOrderTraversal(foo, new ArrayDeque<>());
    }
}