二叉树的遍历

二叉树有很多种，二叉查找树是其中的一种
二叉查找树在二叉树的基础上增加了以下几个条件。
如果左子树不为空，则左子树上所有节点的值均小于根节点的值
如果右子树不为空，则右子树上所有节点的值均大于根节点的值
左、右子树也都是二叉查找树

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。

二叉树都有哪些遍历方式呢？

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

从更宏观的角度来看，二叉树的遍历归结为两大类。

1. 深度优先遍历（前序遍历、中序遍历、后序遍历）。
2. 广度优先遍历（层序遍历）。

深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。

深度优先遍历

1. 前序遍历（Preorder Traversal）
方法：先访问根节点，然后访问左子树，最后访问右子树。在访问左、右子树的时候，同样，先访问子树的根节点，再访问子树根节点的左子树和右子树，这是一个不断递归的过程。
理解：前序遍历的特点就是遍历根节点的同时，在访问左节点时判断是否左节点为根节点，找到最小左字数，然后按照根节点，左子树，右子树的顺序遍历

前序遍历.gif
应用场景：运用最多的场合包括在树里进行搜索以及创建一棵新的树。

2. 中序遍历（Inorder Traversal）
方法：先访问左子树，然后访问根节点，最后访问右子树，在访问左、右子树的时候，同样，先访问子树的左边，再访问子树的根节点，最后再访问子树的右边。
理解：中序遍历的主要特别点就是遍历过程是一个从小到大的过程，根据左<中<右的特点，依大小顺序遍历

中序遍历.gif

应用场景：最常见的是二叉搜索树，由于二叉搜索树的性质就是左孩子小于根节点，根节点小于右孩子，对二叉搜索树进行中序遍历的时候，被访问到的节点大小是按顺序进行的。

3. 后序遍历（Postorder Traversal）
方法：先访问左子树，然后访问右子树，最后访问根节点。
理解：仿佛修叶子，从左向右，把最低端的叶子修剪

后序遍历.gif
应用场景：在对某个节点进行分析的时候，需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行，好比你在修剪一棵树的叶子，修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。

递归方式代码实现：
二叉树，每个根节点下必有左、右两个子树，所以二叉树可以拆分为n个只含有一个根节点、左子树、右子树的最小二叉树。基于递归的算法思想，只需要根据遍历规则顺序输出最小二叉树，然后不断的自调。
具体代码：

/**
* 构建二叉树
* @param inputList 输入序列
*/
public static TreeNode createBinaryTree(LinkedList<Integer>inputList){
    TreeNode node = null;
    if(inputList==null || inputList.isEmpty()){
        return null;
    }
    Integer data = inputList.removeFirst();
    if(data != null){
        node = new TreeNode(data);
        node.leftChild = createBinaryTree(inputList);
        node.rightChild = createBinaryTree(inputList);
    }
    return node;
}

/**
* 二叉树前序遍历
* @param node 二叉树节点
*/
public static void preOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    System.out.println(node.data);
    preOrderTraveral(node.leftChild);
    preOrderTraveral(node.rightChild);
}

/**
* 二叉树中序遍历
* @param node 二叉树节点
*/
public static void inOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    inOrderTraveral(node.leftChild);
    System.out.println(node.data);
    inOrderTraveral(node.rightChild);
}


/**
* 二叉树后序遍历
* @param node 二叉树节点
*/
public static void postOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    postOrderTraveral(node.leftChild);
    postOrderTraveral(node.rightChild);
    System.out.println(node.data);
}


/**
* 二叉树节点
*/
private static class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;

    TreeNode(int data) {
        this.data = data;
    }
}

public static void main(String[] args) {
    LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
    TreeNode treeNode = createBinaryTree(inputList);
    System.out.println(" 前序遍历：");
    preOrderTraveral(treeNode);
    System.out.println(" 中序遍历：");
    inOrderTraveral(treeNode);
    System.out.println(" 后序遍历：");
    postOrderTraveral(treeNode);
}

在代码的main函数中，通过{3,2,9,null,null,10,null,null,8,null,4}这样一个线性序列，构建成的二叉树如下。

image.png

非递归代码实现：
基本思想：
依据遍历规则将左节点依次入栈，然后利用栈的回溯性，找到非叶子节点的右节点
具体代码：

/**
* 二叉树非递归前序遍历
* @param root 二叉树根节点
*/
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子，并入栈
        while (treeNode != null){
            System.out.println(treeNode.data);
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
}

/**
* 二叉树非递归中序遍历
* @param root 二叉树根节点
*/
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子，并入栈
        while (treeNode != null){
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子，则弹出栈顶节点，输出节点，找右孩子
        //如果没有右孩子，则取栈顶节点，输出节点，即位前一个左孩子的根节点，再找右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            System.out.println(treeNode.data);
            treeNode = treeNode.rightChild;
        }
    }
}
//后序遍历有待开发

广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”，那么广度优先遍历则恰恰相反：先在各个方向上各走出1步，再在各个方向上走出第2步、第3步……一直到各个方向全部走完。
层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

image.png

上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。
广度优先遍历要借助一个数据结构来辅助工作，这个数据结构就是队列。
具体思想就是：从上到下，遍历队列，输出节点的同时，将节点的左右非空孩子节点入队，根据队列先进先出的特点，则遍历过程就是一个按照层级的输出过程。
具体代码如下：

/**
* 二叉树层序遍历
* @param root 二叉树根节点
*/
public static void levelOrderTraversal(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    //先将根节点入队
    queue.offer(root);
    while(!queue.isEmpty()){
        //按入队顺序出队输出
        TreeNode node = queue.poll();
        System.out.println(node.data);
        //将左右非空孩子节点入队
        if(node.leftChild != null){
            queue.offer(node.leftChild);
        }
        if(node.rightChild != null){
            queue.offer(node.rightChild);
        }
    }
}