二叉树遍历

1、二叉树遍历

1. 二叉树的性质：二叉树（binary tree）是指树中节点的度不大于2的有序树，即每个结点都不能有多于两个结点。如下图所示为一颗二叉树：
   

2. 二叉树的遍历分为先序遍历、中序遍历、后序遍历。先序、中序、后序是对于根节点（父节点）访问顺序来确定的。

3. 先序遍历思想：先访问根结点；再访问当前结点的左子树；再访问当前节点的右子树。如上图的二叉树先序遍历为：1，2，4，5，3，6，7

4. 中序遍历思想：先访问当前结点的左子树；再访问当前节点；最后访问当前节点的右子树。如上图二叉树中序遍历为：4，2，5，1，6，3，7

5. 后续遍历思想：先访问当前节点的左子树；再访问当前节点的右子树；最后访问当前节点。如上图二叉树后序遍历为：4，5，2，6，7，3，1

2、二叉树遍历递归实现

根据二叉树的性质，二叉树中每个结点拥有结点数据、左节点（左孩子）、右节点（右孩子）三部分组成，所以二叉树结点的结构定义为为：

	// 二叉树节点结构
    class Node<T> {
        T value;
        Node left;
        Node right;
    }

二叉树的递归实现很容易理解，就是按照遍历的顺序依次输出打印节点，如先序遍历，从根结点开始，因先序遍历是先访问根结点的，所以遍历时是先打印根结点，再依次对应左子树、右子树看成一棵树，依次遍历。而中序遍历是在遍历左节点之后再遍历该结点。即针对父节点的遍历先后顺序，来输出该节点的值。其遍历详细流程说明如图所示：可知最终得到的顺序为1，2，4，5，3，6，7。

同理，其中序遍历详细流程如图所示：可知最终得到的中序遍历顺序为：

后序遍历亦是如此，只是当遇到无左右结点的时，该节点所在的上一层子树中，先打印该节点，再打印该节点的兄弟节点即其父节点（头结点）的右子树，其次打印父节点。

根据上述各遍历的方法，二叉树的先序、中序、后序遍历的实现代码如下：

	//递归
    // 先序遍历
    // 每一棵子树都是先打印头，再打印左， 再打印右 （头左右）  
    public static void preOrderRecur(Node head) {
        if (head != null) {
            System.out.print(head.value   " ");
            posOrderRecur(head.left);
            posOrderRecur(head.right);
        }
    }

    // 中序遍历
    // 每一棵子树都是先打印左，再打印头，再打印右 （左头右）
    public static void inOrderRecur(Node head) {
        if (head != null) {
            inOrderRecur(head.left);
            System.out.print(head.value   " ");
            inOrderUnRecur(head.right);
        }
    }

    // 后序遍历
    // 每一棵子树都是先打印左，再打印右，再打印头 （左右头）
    public static void posOrderRecur(Node head) {
        if (head != null) {
            posOrderUnRecur(head.left);
            posOrderUnRecur(head.right);
            System.out.print(head.value   " ");
        }
    }

3、二叉树遍历非递归实现

二叉树的先、中、后序遍历的非递归实现需要用到栈的思想，借助栈的存储结构来遍历二叉树各节点并按各种遍历方式得到遍历的相应顺序。栈的性质是：先进后出，后进先出。

1）先序遍历

先序遍历非递归的思想：准备一个栈，先将头结点放入栈中，每次：
1) 从 栈中 弹出 一个节点cur
2) 打印 处理 cur
3) 先右再左（如果该节点有左右节点，则先将右节点压入栈中，再将左节点放入栈中）
4) 周而复始，重复

先序遍历非递归的遍历流程示例：

先序遍历非递归代码实现：

// 非递归                                                             
// 先序遍历                                                            
// 准备一个栈，先将头结点放入栈中，每次：                                             
// 1) 从 栈中 弹出 一个节点cur                                              
// 2) 打印 处理 cur                                                    
// 3) 先右再左（如果该节点有左右节点，则先将右节点压入栈中，再将左节点放入栈中）                        
// 4) 周而复始，重复                                                      
public static void preOrderUnRecur(Node head) {                    
    System.out.println("pre-order:");                              
    if (head != null) {                                            
        Stack<Node> stack = new Stack<>(); // 备用栈：先进后出             
        stack.add(head); // 压入头结点                                  
        while (!stack.isEmpty()){                                  
            head = stack.pop();  // 1) 从 栈中 弹出 一个节点cur             
            System.out.print(head.value   " ");  // 2) 打印 处理 cur   
            if (head.right != null) {                              
                stack.push(head.right);  // 将右节点压入栈中               
            }                                                      
            if (head.left != null) {                               
                stack.push(head.left);  // 再将左节点放入栈中               
            }                                                      
        }                                                          
    }                                                              
    System.out.println();                                          
}                                                                  

2）后序遍历

后序遍历非递归的思想： 准备两个栈： 栈 收栈，先将头结点放入 栈 中，每次：
1) 从 栈中 弹出 一个节点cur
2) 将 节点 cur 弹出， 放入 收栈 中
3) 先左再右（如果该节点有左右节点，则先将左节点压入 栈中，再将右节点放入 栈中）
4) 周而复始，重复
因为栈是 先进后出，后序遍历顺序是 左右头，即在 收栈的顺序应该是：头右左，
且一开始头就先 放入栈中 并 弹出放入 收栈 所以进 栈 的顺序是 头左右
最终，收栈 的逆序 就是后序遍历，只须依次执行出栈

后序遍历非递归的遍历流程示例：




后序遍历非递归代码实现：

    // 后序遍历
    // 准备两个栈： 栈 收栈，先将头结点放入 栈 中，每次：
    // 1) 从 栈中 弹出 一个节点cur
    // 2) 将 节点 cur 弹出， 放入 收栈 中
    // 3) 先左再右（如果该节点有左右节点，则先将左节点压入 栈中，再将右节点放入 栈中）
    // 4) 周而复始，重复
    // 因为栈是 先进后出，后序遍历顺序是 左右头，即在 收栈的顺序应该是：头右左，
    // 且一开始头就先 放入栈中 并 弹出放入 收栈 所以进 栈 的顺序是 头左右
    // 最终，收栈 的逆序 就是后序遍历，只须依次执行出栈
    public static void posOrderUnRecur(Node head) {
        System.out.println("pos-order");
        if (head != null) {
            Stack<Node> s1 = new Stack<>();  // 栈
            Stack<Node> s2 = new Stack<>();  // 收栈
            s1.push(head);  // 先将头结点放入
            while (!s1.isEmpty()) {
                head = s1.pop();   // 节点 cur 弹出
                s2.push(head);  // 放入 收栈 中
                if (head.left != null) {
                    s1.push(head.left);  // 先将左节点压入 栈中
                }
                if (head.right != null){
                    s1.push(head.right);  // 再将右节点放入 栈中
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value   " ");
            }
        }
        System.out.println();
    }

3）中序遍历

中序遍历非递归的思想： 准备一个栈，从 根结点开始，每次：
1) 每棵子树整棵树左边界 依次 进栈
2) 依次弹出的过程中，打印，
3) 对弹出节点的右节点 周而复始，重复

中序遍历非递归的遍历流程示例：

中序遍历非递归代码实现：

    // 中序遍历
    // 准备一个栈，从 根结点开始，每次：
    // 1) 每棵子树整棵树左边界 依次 进栈
    // 2) 依次弹出的过程中，打印，
    // 3) 对弹出节点的右节点 周而复始，重复
    //
    public static void inOrderUnRecur(Node head) {
        System.out.println("in-order:");
        if (head != null) {
            Stack<Node> stack = new Stack<>();  // 栈
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);  // 头结点开始 进栈
                    head = head.left;  // 获取左节点 进栈 直至无左节点
                } else {
                    head = stack.pop();  // 弹出一个节点
                    System.out.print(head.value   " ");  // 打印
                    head = head.right;  // 对弹出节点的右节点 进行重复操作
                }
            }
        }
        System.out.println();
    }

4、二叉树宽度遍历

宽度遍历就是 从上到下，从左到右依次逐层遍历节点，

实现宽度遍历的思想：准备一个队列（先进先出）

1)先把头节点放入队列中

2)每次弹出一个，打印

3)对于弹出的节点，先把弹出节点的左节点放入队列、再把其右节点放入队列（没有左右节点就不放）

宽度遍历的遍历流程示例：

宽度遍历代码实现：

    // 宽度遍历 ：用队列
    public static void width(Node head) {
        if (head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();  // 队列，先进先出
        queue.add(head);  // 先将头结点放到队列中
        while (!queue.isEmpty()){
            Node cur = queue.poll();  // 从队列中 出列一个节点
            System.out.println(cur.value);  // 打印
            if (cur.left != null){  // 如果弹出的该节点有左节点，则将左节点放到队列中
                queue.add(cur.left);
            }
            if (cur.right != null) { // 如果弹出的该节点有右节点，则将右节点放到队列中
                queue.add(cur.right);
            }
        }
    }

这篇好文章是转载于：学新通技术网