二叉树遍历

二叉树的遍历之前也看过，但好记性不如烂笔头，记录下吧

二叉树定义：

二叉树遍历：

有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

四种遍历思想：

前序：根–>左子树–>右子树

中序：左子树–>根–>右子树

后序：左子树–>右子树–>根

层次遍历：按层一层层遍历

例如，求下面二叉树的各种遍历

代码实现

首先查看二叉树结构的定义：

package com.syj.test.tree;

import lombok.Data;

/**
 * Created by syj on 2018/12/25.
 */
@Data
public class BinaryTree {

    BinaryTree(String val) {
        this.val = val;
    }

    //当前节点值
    private String val;
    //左子树
    private BinaryTree left;
    //右子树
    private BinaryTree right;
}

各种遍历

前中后序遍历采用递归的方式，只是在输出的地方不同，其他地方一样，大家体会下为什么这样做。
广度优先，采用的是队列的方式，按层 先进先出。

package com.syj.test.tree;

import java.util.LinkedList;

/**
 * Created by syj on 2018/12/25.
 *
 */
public class Traversal {

    public static void main(String[] args) {
        BinaryTree node1 = new BinaryTree("1");
        BinaryTree node2 = new BinaryTree("2");
        BinaryTree node3 = new BinaryTree("3");
        BinaryTree node4 = new BinaryTree("4");
        BinaryTree node5 = new BinaryTree("5");
        BinaryTree node6 = new BinaryTree("6");
        BinaryTree node7 = new BinaryTree("7");
        BinaryTree node8 = new BinaryTree("8");

        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node5.setLeft(node7);
        node5.setRight(node8);
        node3.setRight(node6);

        //前序遍历
//        preoder(node1);
        //中序遍历
//        inOrder(node1);
        //后续遍历
//        postOrder(node1);
        //广度优先
        brandthFirst(node1);
    }

    /**
     * 前序遍历(深度优先)：根-->左子树-->右子树
     * @param node
     * @result 1-->2-->4-->5-->7-->8-->3-->6-->
     */
    private static void preoder(BinaryTree node) {
        if (node != null) {
            System.out.print(node.getVal()+"-->");
            BinaryTree left = node.getLeft();
            if (left != null) {
                preoder(left);
            }

            BinaryTree right = node.getRight();
            if (right != null) {
                preoder(right);
            }
        }
    }

    /**
     * 中序遍历(深度优先):左子树-->根-->右子树
     * @param node
     * @result 4-->2-->7-->5-->8-->1-->3-->6-->
     */
    private static void inOrder(BinaryTree node) {
        if (node != null) {
            BinaryTree left = node.getLeft();
            if (left != null) {
                inOrder(left);
            }

            System.out.print(node.getVal()+"-->");

            BinaryTree right = node.getRight();
            if (right != null) {
                inOrder(right);
            }
        }
    }

    /**
     * 后续遍历(深度优先)：左子树-->右子树-->根
     * @param node
     * @result 4-->7-->8-->5-->2-->6-->3-->1-->
     */
    private static void postOrder(BinaryTree node) {
        if (node != null) {
            BinaryTree left = node.getLeft();
            if (left != null) {
                postOrder(left);
            }

            BinaryTree right = node.getRight();
            if (right != null) {
                postOrder(right);
            }

            System.out.print(node.getVal()+"-->");
        }
    }

    /**
     * 广度优先
     * @param node
     * @result 1-->2-->3-->4-->5-->6-->7-->8-->
     */
    private static void brandthFirst(BinaryTree node) {
        LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();
        queue.add(node);
        while (!queue.isEmpty()) {
            BinaryTree curNode = queue.poll();
            System.out.print(curNode.getVal()+"-->");

            BinaryTree left = curNode.getLeft();
            if (left != null) {
                queue.add(left);
            }

            BinaryTree right = curNode.getRight();
            if (right != null) {
                queue.add(right);
            }
        }
    }
}

参考：https://blog.****.net/My_Jobs/article/details/43451187