二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现

二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现

提示：今天开始，系列二叉树的重磅基础知识和大厂高频面试题就要出炉了，咱们慢慢捋清楚！

---

文章目录

• 二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
• • @[TOC](文章目录)
• 二叉树
• 二叉树的递归先序、中序、后序遍历
• 递归序：二叉树递归必定要3次见面
• 二叉树的非递归先序、中序、后序遍历
• • 非递归先序遍历
  • 非递归后序遍历
  • 非递归中序遍历
• 总结

二叉树

啥是二叉树？
就是双指针，只向下指的，无环的链表

二叉树的节点：

public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }

一颗合格的二叉树，无环，往下指，只有2个指针，【多个指针就是多叉树了，比如前缀树】

叶节点的左右指针全是null
造一颗二叉树：

//构造一颗树，今后方便使用
    public static Node generateBinaryTree(){
        //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        Node head = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        head.left = n2;
        head.right = n3;
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n2.left = n4;
        n2.right = n5;
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        n3.left = n6;
        n3.right = n7;
        return head;
    }

关于二叉树，咱们可有得说了，
要学二叉树的遍历，包括先序，中序，后序，按层遍历，
这些有可用递归实现，和非递归实现
后面我们还要学二叉树的序列化，反序列化
寻找二叉树的后继节点、前驱节点
树形动态规划DP：二叉树的递归套路
各种关于二叉树的知识点……

---

二叉树的递归先序、中序、后序遍历

先序遍历：打印顺序是头、左、右
中序遍历：打印顺序是左、头、右
后序遍历：打印顺序是左、右、头

比如：

先序遍历：1 2 4 5 3 7 8
中序遍历：4 2 5 1 7 3 8
后序遍历：4 5 2 7 8 3 1

三者的递归函数遍历打印函数很简单：
先打印头，然后是左树，然后是右树

//先序遍历打印
    public static void prePrint(Node head){
        if(head == null) return;//不管是头还是叶节点，这就是递归的终止条件
        //先打印头，再打印左子树，再打印右子树
        System.out.print(head.value +" ");
        prePrint(head.left);
        prePrint(head.right);
    }
    //中序遍历打印
    public static void inPrint(Node head){
        if(head == null) return;
        //中序遍历，先打印左边，再打印头，再打印右边
        inPrint(head.left);
        System.out.print(head.value +" ");
        inPrint(head.right);
    }
    //后序遍历打印
    public static void postPrint(Node head){
        if(head == null) return;
        //后序遍历打印，先打印左边，再打印右边，最后打印头
        postPrint(head.left);
        postPrint(head.right);
        System.out.print(head.value +" ");
    }

测试一波：

public static void test(){
        Node cur = generateBinaryTree();
        prePrint(cur);
        System.out.println();
        inPrint(cur);
        System.out.println();
        postPrint(cur);
    }
    public static void main(String[] args) {
        test();
//        test2();
    }

看结果：

**1** 2 4 5 3 6 7 
4 2 5 **1** 6 3 7 
4 5 2 6 7 3 **1** 

递归序：二叉树递归必定要3次见面

递归序：调用递归函数f(head)
一定要三次与head见面

递归，首先来到节点1，然后去左子树，
左子树首先见到节点2，然后去左子树，
左子树首先见到节点4，然后去左子树，见到null，返回
再次见到4，再去4的右子树，见到null，返回
再次见到4，然后返回，再次见到2，然后去2的右子树，
首次见到5，然后去5的左子树，见到null，返回
再次见到5，然后去5的右子树，见到null，返回
再次见到5，然后返回，再次见到2，
返回，再次见到1，去1的右子树，见到3
去3的左子树，见到6，去6的左子树，见到null返回再次见到6，
去6的右子树，见到7，去7的左子树，null，返回，再次见到7
去7的右子树，见到null，返回再次见到7，返回再次见到6，
再返回，再次见到1,
递归到此结束

发现，每一个节点，f都会访问它3次。
先序遍历：第一次见面就打印
中序遍历：第二次见面打印
后序遍历：第三次见面打印

//左神汇总一波理解这个遍历的问题
    //树长啥样呢
    //          1
    //        2   3
    //       4 5 6 7
    //递归序：递归总会走这么一个顺序，每一个节点都会遇见3次：
    //走：1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,6,7,7,7,3,1
    //每一个点：首先来到头遇到第一次，然后去左边访问回来又遇见一次，然后去右边访问回来在遇见一次，3次
    //第一次遇到一个点，打印它：则先序遍历
    //第二次遇到一个点，打印它，则中序遍历
    //第三次遇到一个点，打印它，则后续遍历
    //总结：也就是先，中，后，三种遇见打印叫先中后序的遍历；
    public static void f(Node head){
        if(head == null) return;
        //第一次遇见就打印的话，先序遍历
        //System.out.print(head.value +" ");
        f(head.left);
        //第二次遇见打印的话，中序遍历
        //System.out.print(head.value +" ");
        f(head.right);
        //第三次遇见打印的话，后序遍历
        System.out.print(head.value +" ");
    }

    public static void test2(){
        Node cur = generateBinaryTree();
        f(cur);

    }
    public static void main(String[] args) {
        test();
//        test2();
    }

你分别注释打印的位置，
就能得到结果。

---

二叉树的非递归先序、中序、后序遍历

任何递归实现的代码，都能通过非递归实现
既然是一个遍历的事情
就可以让栈来实现
当节点x，出来访问时，它左子右子可以陆续压栈，由于栈能先进后出，所以压入的顺序，决定了d出的顺序
从而达到控制x的左子和右子打印的顺序
（1）如果遇到x打印，然后先压右子，再压左子，d出时，必定先d出左子，再d出右子
这不就是头、左、右吗？——先序遍历

（2）如果遇到x打印，然后先压左子，再压右子，d出时，必定先d出右子，再d出左子
这不就是头、右、左吗？
此时，你再逆序一下：左、右、头——后序遍历
巧了吧？

（3）关于中序遍历，比较复杂，但是也就是用栈巧妙地控制进出栈的顺序
咱们这么想
我们中序遍历打印顺序是左，头，右
那么先让头别打印
A：我们先压头x，然后去x的左树 *** 作，不断地，压头，继续去左树
然后遇到null后，返回，打印左
然后打印头，然后去右树压x，继续循环A
这样的话，打印顺序就是左、头、右
在代码中，就是控制if else条件，进入左树和右树【这玩意死记硬背，记不了算了】

非递归先序遍历

自己手撕代码撕清楚

//复习（1）如果遇到x打印，然后先压右子，再压左子，d出时，必定先d出左子，再d出右子
    //这不就是头、左、右吗？——先序遍历
    public static void unRecurrentPrePrint(Node head){
        if (head == null) return;

        Stack<Node> stack = new Stack<>();
        stack.push(head);//先压头
        while (!stack.isEmpty()){
            //首先打印头
            Node cur = stack.pop();
            System.out.print(cur.value + " ");
            //然后反着压，先压右边，再压左边，回头就是左右顺序出
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
    }

1 2 4 5 3 6 7 

非递归后序遍历

自己想清楚思想，然后手撕代码

//复习：（2）如果遇到x打印，然后先压左子，再压右子，d出时，必定先d出右子，再d出左子
    //这不就是头、右、左吗？
    //此时，你再逆序一下：左、右、头——后序遍历
    public static void unRecurrentPostPrint(Node head){
        if (head == null) return;

        //俩栈，一个控制压入顺序，一个控制逆序
        Stack<Node> inStack = new Stack<>();
        Stack<Node> backStack = new Stack<>();
        inStack.push(head);//先入头，再入左右--逆序放入back：头右左，输出左右头
        while (!inStack.isEmpty()){
            Node cur = inStack.pop();
            backStack.push(cur);//逆序放

            if (cur.left != null) inStack.push(cur.left);//先左
            if (cur.right != null) inStack.push(cur.right);//后右--出去就是头右左，back才能是左右头
        }

        //逆序输出
        while (!backStack.isEmpty()){
            System.out.print(backStack.pop().value +" ");//back才能是左右头
        }
    }

非递归中序遍历

//这样的话，打印顺序就是左、头、右
    public static void unRecurrentInPrint(Node head){
        if (head == null) return;

        Stack<Node> stack = new Stack<>();
        //只要是左边不空，去左树
        while (!stack.isEmpty() || head != null){
            //为啥要加head呢？？
            if (head != null) {
                //先左树
                stack.push(head);
                head = head.left;//可能就去遇到了null
            }else {
                //如果左树是null，head是叶节点
                //说明树的第一个左叶节点该打印了，然后去打印头，再去右树
                head = stack.pop();
                System.out.print(head.value +" ");
                head = head.right;
            }
        }
    }

测试一下：

public static void test2(){
        //造树
        Node head = generateBinaryTree1();
        //先序
        unRecurrentPrePrint(head);
        System.out.println();
        //后序
        unRecurrentPostPrint(head);
        System.out.println();
        //中序
        unRecurrentInPrint(head);

    }


    public static void main(String[] args) {
//        test();
        test2();
    }

1 2 4 5 3 6 7 先序
4 5 2 6 7 3 1 后序
4 2 5 1 6 3 7 中序

---

总结

提示：重要经验：

1）递归序，3次见面，第一次见面打印叫先序遍历，第二次见面打印叫中序遍历，第三次见面打印叫后序遍历
2）非递归实现中，先序和后序是相反的，但是中序遍历挺难理解，但是核心思想也就是先去左树，再打印头，然后再去右树。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。