在数据结构树中我们最常用的就是二叉树，二叉树的分类又有很多种，利用好二叉树我们可以快速的从大数据量中找到我们所需的数据。

前面我们介绍了树，二叉树顾名思义就是每个数据节点最多有两个叉，也就是每个数据节点最多是有两个孩子节点。

特点：

1. 每个节点最多有两个孩子节点。
2. 即使节点没有孩子节点，新添加的节点也要区分是该节点左孩子或者右孩子。

特点：树中所有的非叶子节点都有左孩子和右孩子。所有叶子节点都在同一层上。

定义： 对一个有n个节点的二叉树， 按层级顺序编号， 则所有节点的编号为从1到n。 如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节
点位置相同， 则这个二叉树为完全二叉树。

二叉树的遍历作为单独一篇是因为我们在使用二叉树结构的时候不可避免的需要数据的遍历，但二叉树又不是线性结构那样遍历很简单，所以这里单独介绍。

二叉树的遍历一般有四种

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层级遍历

四种遍历又分

1. 深度遍历 （ 前序、中序、后序）
2. 广度遍历 （层级)

深度与广度这里代表的是一种复杂数据结构的遍历思想，深度就是已深度为优先从头查到底，广度就是已层级为优先一层一层查。

前序遍历的遍历顺序是：根节点–>左子树–>右子树

遍历的步骤：

1. 先输出了根节点。
2. 再找到根节点的左子树，在这个左子树中，节点2又属于左子树的根节点，所以输出节点2.
3. 再找节点2的左子树，因为在代码中我们不知道节点4是否有左子树或者右子树，所以节点4也可以看成是节点2左子树的根节点，输出节点4.
4. 遍历到了节点4，节点4无左子树，无右子树，说明以节点4为根节点的子树已遍历完，也就是节点2的左子树遍历完成，则需要开始遍历节点2的右子树，节点2的右子树的根节点为5，则输出节点5
5. 节点5的左右子树无，则节点2的右子树遍历完成，也就是节点1的左子树遍历完成。开始遍历节点1的右子树，右子树的根节点为3，则输出节点3.
6. 以节点3为根节点的子树有左子树，则先遍历节点3的左子树，节点3左子树根节点为节点6，则输出节点6.
7. 节点6无左右子树，则以节点3为子树的左子树遍历完成，开始遍历节点3的右子树，右子树根节点为节点7，则输出节点7.
8. 以节点7为根节点的子树无左右子树则遍历完成。

中序遍历的顺序是: 左子树–>根节点—>右子树

遍历步骤：有前序为例，

1. 查找根节点左子树，再查找左子树的左子树，一次类推，直到查到以节点4为根节点的子树，这时节点4无左子树，按照左-根-右原则，输出子树根节点4.
2. 输出节点4后，以节点4为根的子树无右子树，则以节点4为根节点的子树遍历完毕，返回父节点2，已节点2为根节点的左子树节点4已输出，则输出根节点2.
3. 以节点2为根节点的子树，左子树、根节点都已输出，这里开始遍历节点2的右子树，以节点5为根节点的子树没有左子树，所以输出根节点5.
4. 以节点5为根节点的子树没有右子树，则已节点2为根节点的子树遍历完成，也就是以节点1为根节点的左子树遍历完成，输出根节点1.
5. 以左-根-右顺序，开始输出根节点的右子树，以节点3为根节点的子树存在左子树则一次查找到左子树，直到以节点6为根节点的子树，节点6无左子树，则输出根节点6.
6. 以节点6为根的子树没有右子树则返回父节点3，以节点3为根节点的子树的左子树已输出完毕，现在输出根节点3。
7. 已节点3为根节点的左子树–根节点已输出，现在输出右子树，以节点7为根节点的子树没有左子树则输出根节点7.
8. 节点7无右子树则遍历结束。

后序遍历的顺序为： 左子树–>右子树–>根节点

后续遍历不再详细介绍，根据前面的前序遍历、中序遍历都可以猜出来。

我看从上面可以看到所谓的 前序、中序、后序都是相对于根节点来说的，我们把每个节点和它的孩子看成一个树，这个节点可以看成树的根节点也可以看成父节点树的孩子节点。

我们每次更具前序、中序、后续遍历子树再输出这个子树的根节点。在每个子树中我们那步输出根节点就属于什么遍历。

public class ForeachBinaryTree {


    private static final String EMPTY = "   ";

    /**
     * 二叉树遍历，前序遍历
     *
     * @param root
     */
    public static void rootLeftRight(BinaryTreeNode root) {
        println("----------------------\n前序遍历:");
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
                print(node.getKey() + EMPTY);
                stack.push(node);
                node = node.getLeft();
            } else {
                BinaryTreeNode tem = stack.pop();
                node = tem.getRight();
            }
        }

        println("\n----------------------");
    }


    /**
     * 二叉树遍历，中序遍历
     *
     * @param root
     */
    public static void leftRootRight(BinaryTreeNode root) {
        println("----------------------\n中序遍历:");
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
                stack.push(node);
                node = node.getLeft();
            } else {
                BinaryTreeNode n = stack.pop();
                print(n.getKey() + EMPTY);
                node = n.getRight();
            }
        }

        println("\n----------------------");
    }


    /**
     * 二叉树遍历，后序遍历
     *
     * @param root
     */
    public static void leftRightRoot(BinaryTreeNode root) {
        println("----------------------\n后序遍历:");
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = root;
        BinaryTreeNode pre = null;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.getLeft();
            } else {
                BinaryTreeNode n = stack.peek();
                BinaryTreeNode r = n.getRight();
                if (r == null || r == pre) {
                    print(n.getKey() + EMPTY);
                    stack.pop();
                    pre = n;
                    node = null;
                } else {
                    node = r;
                }
            }
        }

        println("\n----------------------");
    }


    /**
     * 层级遍历
     * @param root
     */
    public static void level(BinaryTreeNode root) {
        println("----------------------\n层级遍历:");
        ArrayList<BinaryTreeNode> nodes = new ArrayList<>();
        ArrayList<BinaryTreeNode> temp = new ArrayList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            for (int i = 0; i < nodes.size(); i++) {
                BinaryTreeNode n = nodes.get(i);
                print(n.getKey() + EMPTY);
                if (n.getLeft() != null) {
                    temp.add(n.getLeft());
                }
                if (n.getRight() != null) {
                    temp.add(n.getRight());
                }
            }
            nodes.clear();
            nodes.addAll(temp);
            temp.clear();
        }
        println("\n----------------------");
    }


    private static void println(Object o) {
        System.out.println(o);
    }

    private static void print(Object o) {
        System.out.print(o);
    }
}