数据结构：带你进入二叉树的新世界（上篇）

✨个人主页： 不漫游-CSDN博客

前言

前面的咱们学习的都是线性表，但在实际生活中，非线性的才是更为常见的，今天要介绍的二叉树便属于此类~

什么是树？

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

效果就是这样 

 

这里就是要注意一点：

 在树形结构中，子树之间不能有交集，否则就不是树形结构

像下面这样的就不是树形结构 

一些关于树的基本概念 

结点的度：一个结点含有子树的个数称为该结点的度； 如图：B的度为1
树的度：一棵树中，所有结点度的最大值称为树的度； 如图：树的度为3
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、....H、I等节点为叶子结点。
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如图：A是整棵树的根节点

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推，看下图。
树的高度或深度：树中结点的最大层次； 如图：树的高度为4

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

 

二叉树的五种基本形态

要注意这些可都是二叉树哦~ 

两种特殊的二叉树

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

 

这里有个小技巧：如果一棵二叉树的层数为K，且结点总数是(2^k)-1 ，则它就是满二叉树。 做题常用的结论！

完全二叉树

有n个结点的二叉树，当且仅当其每一个结点都与同样深度的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。

 

要注意的是满二叉树是一种特殊的完全二叉树！

二叉树常用的性质（最好理解记忆）

性质一：一棵非空二叉树的第i层上最多有2^(i-1) (i>0)个结点

性质二：一棵深度为 k 的二叉树至多有 (2^k)-1 个结点

性质三： 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

性质四： 具有n个结点的完全二叉树的深度k为 log(n+1)上取整(即不大于)

性质五：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
1.若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
2.若2i+1<n，左孩子序号：2i+1，否则无左孩子
3.若2i+2<n，右孩子序号：2i+2，否则无右孩子

一条一条来理解性质五：

1.i=1显然是根节点

2.对于节点6：2x6+1>总结点数10；所以没有左孩子，同理2x6+2>10，也没有右孩子

二叉树的遍历

前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树， 再前序遍历右子树。简称根左右。

 

中序遍历

先访问根的左子树--->对应子树的根节点--->根的右子树，简称左根右。

后序遍历

先访问根的左子树--->根的右子树--->根节点，简称左右根。

 

层序遍历 

自上而下，自左至右逐层访问树的结点的过程就是层序遍历

 

一些练习帮助理解 

1.设一课二叉树的中序遍历序列:badce，后序遍历序列:bdeca，则二叉树前序遍历序列是__

 解析：

首先，根据后序遍历序列"bdeca"的最后一个元素 "a"，确定了根节点为"a"。然后根据中序遍历序列"badce"中根节点"a"的位置，将中序遍历序列分成了左子树"b"和右子树"dce"。在后序遍历序列中，左子树范围为"d"，右子树范围为"e"根就是c。

所以前序遍历就是abcde了 

2..某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF,则按层次输出(同一层从左到右)的序列为____

解析： 

根据后序遍历确定根F,确定中序遍历只有左子树，以此递归，E又是左子树的根，同样也只有左子树，最后便是下面这样：

所以层次遍历就出来了：FEDCBA 

二叉树的基本操作实现

初始化定义

首先定义好左右节点和存储的数据

public class TestBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
 
        public TreeNode(char val) {
            this.val = val;
        }
    }

创建一棵二叉树 

    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
 
        A.left=B;
        A.right=C;
        B.right=E;
        B.left=D;
        E.right=H;
        C.right=G;
        C.left=F;
 
        return A;
    }

画图出来就是这样：

遍历 

这三种遍历方式采用了递归的方式，逐步按照各自的顺序去遍历左子树的左右子树，右子树的左右子树，如此递归和回溯，便完成了~

 前序遍历

    //前序遍历
    public void preorderTraversal(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");  // 首先访问当前节点
            preorderTraversal(node.left);      // 然后递归左子树
            preorderTraversal(node.right);     // 最后递归右子树
        }
    }

中序遍历 

    //中序遍历
    public void InorderTraversal(TreeNode node){
        if(node!=null){
            InorderTraversal(node.left);
            System.out.print(node.val+" ");
            InorderTraversal(node.right);
        }
    }

后序遍历 

    //后序遍历
    public void PostorderTraversal(TreeNode node){
        if(node!=null){
            PostorderTraversal(node.left);
            PostorderTraversal(node.right);
            System.out.print(node.val+" ");
        }
    }

查值是否存在 

少不了要遍历整棵树才行，和之前的思路有一致的地方，那便是递归下去，一直查找左子树和右子树是否有要找的值

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
 
        if (root.val == val) {
            return root;
        }
 
        TreeNode leftResult = find(root.left, val);//查找左子树
        if (leftResult != null) {
            return leftResult;
        }
 
        TreeNode rightResult = find(root.right, val);//查找右子树
        if (rightResult != null) {
            return rightResult;
        }
 
        return null;
    }

获取节点个数 

这道题可以用递归，或者传统的遍历法：

1.若用递归就是左子树的节点数+右子树的节点数+1

2.若用遍历思路，则需要一个变量去记录节点的个数，直到遍历结束返回值输出

    /**
     * 获取树中节点的个数：遍历思路
     */
    public static int usedSize = 0;//记录节点个数
    int size(TreeNode root) {
        if(root==null){
            return 0;
        }
        usedSize++;
        size(root.left);
        size(root.right);
        return usedSize;
    }
 
    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if(root==null){
            return 0;
        }
        int ret=size2(root.right)+size2(root.left)+1;
        return ret;
    }

获取叶子节点个数 

这个和获取节点个数是大同小异，要注意的就是叶子节点的确定条件就是没有左右节点

    /*
     获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0;
 
    void getLeafNodeCount1(TreeNode root) {
        if(root==null){
            return ;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
 
    /*
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if(root==null){
            return 0;
        }
        return getLeafNodeCount2(root.right)+getLeafNodeCount2(root.left);
 
    }

获取某层节点个数 

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

获取二叉树的高度 

大致思路就是先比较左右子树的高度，最高的那个再+1即可，也是用递归的思路，从最底层比到最后只有一个根节点便停止

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return Math.max(left,right)+1;
 
    }

层序遍历 

从上到下，从左到右。从规则中，便可以发现，队列的先进先出是符合这种遍历方式的。

例如：

A->BC->DEF->GHI.可现进栈BC和出栈是一样的，以此类推....

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//入栈
        while(!queue.isEmpty()){
        TreeNode node=queue.poll();//出栈
            System.out.print(node.val + " "); 
        //循环遍历左右子树
        if(node.left!=null){
            queue.offer(node.left);
        }
        if(node.right!=null){
            queue.offer(node.right);
        }
    }
    }

判断是否为完全二叉树 

还记得完全二叉树的特征吗？---->当且仅当其每一个结点都与同样深度的满二叉树中编号从0至n-1的结点一一对应。因此只要层序遍历只要碰到null，那就没有一一对应，那就不是完全二叉树。

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//将树的节点入队
        boolean flag=false;//标志是否出现空节点
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node==null){
                return true;
            }if(flag){
                flag=true;
            }
           //继续入队左右节点
            queue.offer(node.right);
            queue.offer(node.left);
        }
        return true;
        }
    }

总结

其实不难发现，二叉树的左右子树，左右子树的左右子树....就决定递归的方式会适配，所以以后碰到有关二叉树的问题时，试着看看能不能转换成左右子树的问题，或许就茅塞顿开~

看到最后，如果觉得文章写得还不错，希望可以给我点个小小的赞，您的支持是我更新的最大动力