二叉树、递归遍历的白话文讲解

vlambda
2020-03-20

二叉树、递归遍历的白话文讲解

面试中，总有同学被问到二叉树的问题，什么是二叉树，如何遍历一个二叉树，如何知道树的深度，以及神秘的递归

那么，我们今天来讲讲神秘的二叉树及递归在二叉树中的应用

下面提供一个这样的二叉树

二叉树顾名思义就是两个叉的树，只是这个数是倒立的从上到下的放数据，比如说我们有Integer []a={2,4,5,7,1,6,12,32,51,22}; 这样一个数组，其中有10个数，如果将这个数组放入二叉树中这颗树会长成如下图所示这样数是一层一层放的，一层放满左右两个，就再加一层往下放

前序递归: 2,4,7,32,51,1,22,5,6,12 先根节点->后左子树->最后右子树

中序递归: 32,7,51,4,22,1,2,6,5,12 先左子树->后根节点->最后右子树

后序递归: 32,51,7,22,1,4,6,12,5,2 先左子树->后右子树->最后根节点

二叉树先介绍到这里，我们聊聊递归这件事

二叉树、递归遍历的白话文讲解

相信大部分同学对递归是什么倒是好理解，像这张图来说，就是一层一层的递进，那如果说，拿程序的函数来说的话，就是函数自己调用自己，既然自己调用自己，是不是为了防止死循环，必须要设定好一个退出的条件，如果没有非常准确的递归退出条件也就是常说的必须有个出口，如果没有递归的退出条件，那很容易就造成栈溢出这个问题，所以理解递归方法，先理解它的退出条件，通过退出条件返回上一级

像这张图，没有明确的退出递归调用的条件，直接死循环

二叉树、递归遍历的白话文讲解

所以说，使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。

这么一张树形图，很好理解，如果拿万物皆对象来说，首先一个TreeNode节点需要有左右两个节点，以及value变量保存当前值，为了方便后续遍历再保留一个root上一级节点，那么TreeNode节点如下

package cn.wfb.test;
import java.util.ArrayList;
import java.util.List;

/**
*这个节点类由五个属性组成
*   左子树、右子树、当前节点数据、上一级根节点
*  
*/

public class TreeNode {

    Object value;       //数据
    TreeNode left;      //左子树
    TreeNode right;     //右子树
    TreeNode root;      //整颗树的根节点
    public List<TreeNode> datas; //保存所有树节点

    /**
     * 创建树节点在构建树时应用
     */
    TreeNode(TreeNode left,TreeNode right, Object value){
        this.left = left;
        this.right = right;
        this.value = value;
   }

    /**
     * 创建树节点
     * @param value
     */
    TreeNode(Object value){
        this(null,null,value);
   }

    /**
     * 创建空节点用
     * @param value
     */
    TreeNode(){
   }

   /**
     * 通过传入数组创建当前树
     * @param 传入数组
     */
    public void create(Object[] objes){
        datas = new ArrayList<TreeNode>();
        
        // 首先将传入的数组转成树节点，存入datas属性
        for (Object obje : objes) {
            datas.add(new TreeNode(obje));
       }

        // 取出数组第一个作为整棵树的根节点
        root = datas.get(0);

        // 将转换的数节点开始构建二叉树
         /**
     * 思路是：树是左右两个子树，所以循环当前数组长度的一半
           * get(0)是根节点的话，那么get(1)是左子树，get(2)是右子树
           * 那么get(1)的左子树就是get(1*2+1)=get(3)
           *     get(1)的右子树就是get(1*2+2)=get(4)
           * 剩下就是自己循环从0-4的i的值，并设置其左右子树
           */
        for (int i = 0; i < objes.length / 2; i++ ) {
            //左子树
            datas.get(i).left = datas.get(i * 2 + 1);
            //右子树
            if(i * 2 + 2 < datas.size()){
                datas.get(i).right = datas.get(i * 2 + 2);
           }
       }
   }

    /**
     * 前序递归遍历
     * 前序顺序：根节点->左子树->右子树
     * 打印效果 2,4,7,32,51,1,22,5,6,12,对比上面的树图查看
     */
    public void preorder(TreeNode root){
        if(root!=null){  //这个条件就是递归调用出口
            System.out.println(root.value);  //根节点
            preorder(root.left);             //左子树递归调用，直到为null返回上一级，执行右子树探索
            preorder(root.right);            //右子树递归调用后会继续判断是否有左子树，直到为null
       }
   }

    /**
     * 中序递归遍历
     * 中序顺序：左子树->根节点->右子树；
     * 打印效果 32,7,51,4,22,1,2,6,5,12
     */
    public void inorder(TreeNode root){
        if(root!=null){//这个条件就是递归调用出口
            inorder(root.left);
            System.out.println(root.value);
            inorder(root.right);
       }
   }

    /**
     * 后序递归遍历
     * 后序顺序：左子树->右子树->根节点
     * 打印效果 32,51,7,22,1,4,6,12,5,2
     */
    public void afterorder(TreeNode root) {
        if (root != null) {//这个条件就是递归调用出口
            afterorder(root.left);
            afterorder(root.right);
            System.out.println(root.value);
       }
   }

    /**
     * 递归遍历树的深度，左子树-》根节点-》右子树
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root){
        //这个条件就是递归调用出口，非常重要，是理解递归的第一步
        if(root == null){
            return 0;
       }
        int lDepth = maxDepth(root.left); //获取左节点递归
        int rDepth = maxDepth(root.right);
        
        
        /* 以下注释打开后可以从控制台输出,能够看出递归的顺序是,左子树递归直到null返回0后,返回上一级+1处理,再探索右子树
        String t = Optional.ofNullable(root.left).map(p -> "当前节点" + root.value + " 进入左节点" + p.value).orElse(" 节点" + root.value + "的左节点为空");
        System.out.println(t);
        int lDepth = maxDepth(root.left, root);   //左子树
        t = Optional.ofNullable(root.right).map(p -> "当前节点" + root.value + " 进入右节点" + p.value).orElse(" 节点" + root.value + "的右节点为空");
        System.out.println(t);
        int rDepth = maxDepth(root.right, root); //右子树
        //根节点1 + 查看谁的深度大，如果左大返回左子树，如果右大返回右子树
        int ret = 1 + (lDepth > rDepth ? lDepth : rDepth);
        System.out.print("节点" + root.value + " 左子树深度:" + lDepth + " 右子树深度:" + rDepth + " 当前深度:" + ret);
        return ret;
        */

        //放开上面的注释方便我们理解递归如何遍历的二叉树深度，下面这行代码需要注释掉
        return 1 + (lDepth > rDepth ? lDepth : rDepth);
   }

    public TreeNode getRoot() {
        return root;
   }
    public void setRoot(TreeNode root) {
        this.root = root;
   }
}

最后是测试Solution类，可以看到前中后排序及深度

public class Solution {

    public static void main(String[] args) {

        TreeNode node = new TreeNode();        //创建节点对象
        Integer []a={2,4,5,7,1,6,12,32,51,22};       //参照给的二叉树图理解
        node.create(a);                        //通过create方法传入数组创建树

        node.preorder(node.root);       //前序
        //node.inorder(node.root);     //中序
        //node.afterorder(node.root);   //后序

        int maxDepth = node.maxDepth(node.root);
        System.out.println("=深度是="+maxDepth);
   }
}