实现二叉树前序、中序、后序遍历

发表于 分类于 阅读次数：

前言

遍历二叉树是二叉树知识中的基础，有递归版本和非递归版本，这里递归的版本比较容易，所以我们只说前序遍历的递归形式，剩下的中序和后序由读者自行实现。本文着重写非递归形式的遍历。除了前中后序遍历外各位也可以自行实现层序遍历（一层一层遍历）。

前序、中序、后序遍历的定义

最简单的理解

  1. 前序遍历：对于每个节点而言，先输出自身，再输出左子树，最后输出右子树的。(中左右)
  2. 中序遍历：对于每个节点而言，先输出左子树，再输出自身，再输出右子树。（左中右）
  3. 后序遍历：对于每个节点而言，先输出右子树，再输出左子树，再输出自身。（右左中）

我们深入剖析一下这里面到底发生了什么。

每次进入新节点(current)都进行以下操作：

（下面的”操作”为输出或其他行为）

  • 前序遍历：首先操作当前节点current，接着进入并操作current.left，而后返回到current，再进入并操作current.right，最后返回current。

  • 中序遍历：首先进入并操作current.left,接着返回并操作current,再进入current.right并操作,最后返回current。

  • 后序遍历：首先进入并操作current.right,接着返回并操作current，而后再进入current.left并操作，最后返回current。

可以发现，我们在遍历二叉树的时候都会进入*每一个节点(current)三次，
*(①进入current,②从左子树返回current,③从右子树返回current)
而这三次分别对应前中后序遍历。

换一种说法，对于当前节点current,一定会经过3次。

若第一次进入current并进行操作的则是先序遍历。

若第二次进入current并进行操作的则是中序遍历。

若第三次进入current并进行操作的则是后序遍历。

文字过多可能会比较晕，下面看一下例子：

此处仅是一个很简单的例子，读者可自行画一个大一点的树进行观察练习。

递归版本

因为递归版本比较简单，所以此处仅提供前序遍历的递归版本。

1
2
3
4
5
6
7
8
9
10
11
public static void preOrderRecur(Node head) {

        if(head == null)
            return;
        //先打印自身
        System.out.println(head.value);
        //再打印左子树
        preOrderRecur(head.left);
        //再打印右子树
        preOrderRecur(head.right);
    }

非递归版本

先序遍历

  1. 准备一个栈并让根节点入栈。

  2. 把栈顶输出作为current，并输出，然年压入current的左节点，最后压入current的右节点。(因为栈的性质后进先出)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void preOrderUnRecur(Node current) {
        //为什么不用队列？
        //因为队列是按顺序一直往下，树本身就是往下的且不能回头，
        // 但你要遍历所有节点必须要能返回上一层，所以我们用栈。
        if(current != null) {

            Stack<Node> stack = new Stack<>();
            stack.push(current);
            while(!stack.isEmpty()) {
                current = stack.pop();
                System.out.println(current.value);
                //栈顶优先是当前节点的右节点(后进先出)
                if(current.right != null) {
                    stack.push(current.right);
                }
                if(current.left != null) {
                    stack.push(current.left);
                }
            }
        }
    }

中序遍历：

  1. 若当前current不为null，则current入栈,然后向左节点推进(current = current.left)。直到current为null。
  2. 若当前current为null，而栈中仍有值，则pop一个输出，并让其右节点作为current，回到1。
  3. 直到current为null，栈也为空即结束。

建议兄弟萌把整个流程走一遍，这样就有感觉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void inOrderUnRecur(Node current) {
        if(current != null) {
            Stack<Node> stack = new Stack<>();
            
            while(!stack.isEmpty() || current != null) {
                if(current != null) {
                    stack.push(current);
                    current = current.left;
                }else {
                    //左节点为空,就右节点，pop到没有位置
                    current = stack.peek().right;
                    System.out.println(stack.pop());
                }
            }
        }
    }

后序遍历

后序遍历很有意思，他和前序遍历十分相像。

前序遍历的顺序是中左右，而后序遍历为左右中。

回头看一下前序遍历，我们可以把左右的顺序调节一下，变成中右左，再把它倒序，就是我们要的左右中了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void posOrderUnRecur1(Node current) {

        if(current != null){

            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(current);
            while(!stack1.isEmpty()) {
                current = stack1.pop();
                stack2.push(current);
                if(current.left != null) {
                    stack1.push(current);
                }
                if(current.right != null) {
                    stack1.push(current);
                }
            }
            
            while(!stack2.isEmpty()) {
                System.out.println(stack2.pop());
            }
        }

补充：层序遍历

介绍

嘻嘻，没想到吧，我有补充的一天。因为在写序列化的时候，发现自己还漏了一种层序遍历没写，所以来补啦，兄弟萌可以看leetcode:102。有层序遍历定义及其题目。

这里之说以下大致的思路及编码时要注意的细节，因为leetcode官方已经给出了较为详细的解释。那么开始吧。

递归版

  • 大致思路，用一个链表（Levels）装每一层的数据，每一层的数据同样用一个链表来装。也就是这样[1,[2,3],[4,5,6,7]]。相信机智的你已经理解了，下面来实际编码吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> arrayList = new ArrayList<>();
   public List<List<Integer>> levelOrder(TreeNode root) {
       if(root == null) return arrayList;
       level(root, 0);
       return arrayList;
   }
   
   public void level(TreeNode head, int floor){
       if(arrayList.size() == floor) {
           arrayList.add(new ArrayList<Integer>());
       }
       arrayList.get(floor).add(head.val);
       if(head.left != null) {
       //注意在进入左右子树的时候，应该用floor + 1 而不用 ++floor，因为你左子树++floor，而右子树又++，会造成左右子树不在同一层
           level(head.left, floor + 1);
       }
       if(head.right != null) {
           level(head.right, floor + 1);
       }
   }

非递归版

  • 这里我们需要要队列，先把根节点放入队列中，然后遍历这个队列（遍历过程中会有相应的插入）直到队列为空就表明层序遍历结束了。下面说明一下每次遍历队列中的操作
    1. 把队列的头先poll出来(这里把poll出来的节点称作为poller)
    2. 检查poller是否有左右节点，若存在则offer进去。（注意顺序！先左后右）

文字表述仍存在一定疑惑，下面看下图片吧。

把1加入队列中，蓝色节点表示新加入的节点

把1poll出来，与之相应的把1的左右节点加入队列中

把2poll出来，与之相应的把2的左右节点加入队列中

把3poll出来，与之相应的把3的左右节点加入队列中

  • 我们利用队列先进先出的特点把树按从左到右的顺序加入队列中，所以右节点节点永远都不会早于其父节点或左兄弟节点行动。

下面来看下实际代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void levelOrderNoRec(Node root) {
        if(root == null) return;
        Queue<Node> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()) {
            Node poll = queue.poll();
            System.out.println(poll.value);
            if(poll.left != null) {
                queue.offer(poll.left);
            }
            if(poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }