【DS】5.二叉树大总结！

墨蓝 2024-04-03 09:42 26阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、树的相关概念及表示形式
     *  二、二叉树的相关概念及性质
     *   *  基本概念及特点
         *  特殊的二叉树及性质
         *   *  满二叉树：
             *  完全二叉树：
             *  二叉搜索树（BST）
     *  三、二叉树的存储、遍历及基本操作实现
     *   *  二叉树的存储：
         *  二叉树的遍历 ：
         *   *  1.前序遍历【根节点-->左子树-->右子树】
             *  2.中序遍历【左子树-->根节点-->右子树】
             *  3.后序遍历【左子树-->右子树-->根节点】
             *  4.层序遍历
         *  确定二叉树的一些小规律
     *  四、TreeSet的介绍及常用方法介绍
     *   *  二叉树的基本操作
         *  TreeSet方法源码
         *  二叉树常用操作模拟

### 一、树的相关概念及表示形式 ###

\*\*定义：\*\*树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。**形状很像倒挂的树。**

**特点**：

*  根结点没有前驱结点；
 *  除根结点外，其余结点被分成M(M > 0)个互不相交的集合，每个集合又可以看成是一棵树（树是递归定义的）；
 *  每个节点最多有一个前驱/双亲节点，可以有0或者多个后继/孩子节点。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7e8D5fmb-1665045381213)(F:\\typora插图\\image-20221006154345905.png)\]][img-7e8D5fmb-1665045381213_F_typora_image-20221006154345905.png]

***相关概念【非常重要】***

结点的度：一个结点含有子树的个数称为该结点的度。

树的度：一棵树中，所有结点度的最大值称为树的度

叶子结点或终端结点：度为0的结点称为叶结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点

根结点：一棵树中，没有双亲结点的结点

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次

【了解】

非终端结点或分支结点：度不为0的结点

兄弟结点：具有相同父结点的结点互称为兄弟结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟

结点的祖先：从根到该结点所经分支上的所有结点

子孙：以某结点为根的子树中任一结点都称为该结点的子孙  
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

**表示形式**

双亲表示法， 孩子表示法、孩子双亲表示法、**孩子兄弟表示法**【最常用】等等

class Node {
         
        int value;
    	Node firstChild; 
        Node nextBrother;
    }

**应用：**

互不相交的集合例如：文件管理系统

### 二、二叉树的相关概念及性质 ###

#### 基本概念及特点 ####

\*\*定义：\*\*一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。（每棵子树又可以看成是由左子树和右子树构成的）

\*\*特点：\*\*1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。3.根结点没有前驱结点。二叉树是递归定义的，每棵树都是由左子树和右子树组成的，每棵子树也可以看成一棵完整的树。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n3ALfpHt-1665045381215)(F:\\typora插图\\image-20221005100536652.png)\]][img-n3ALfpHt-1665045381215_F_typora_image-20221005100536652.png]

#### 特殊的二叉树及性质 ####

##### 满二叉树： #####

二叉树**每层的结点数都达到最大值**【节点总数是2^k-1个】，则这棵二叉树就是满二叉树。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JrWupRXu-1665045381217)(F:\\typora插图\\image-20221005101302349.png)\]][img-JrWupRXu-1665045381217_F_typora_image-20221005101302349.png]

##### 完全二叉树： #####

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

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CW7GZAvu-1665045381218)(F:\\typora插图\\image-20221005101050738.png)\]][img-CW7GZAvu-1665045381218_F_typora_image-20221005101050738.png]

满二叉树是一种特殊的完全二叉树。

##### 二叉搜索树（BST） #####

定义：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值的二叉树叫做二叉搜索树。

![img][]

二叉搜索树主要支持三个操作：搜索、插入和删除

> 由于本文主要是基础内容的总结，这个二叉搜索树是文章快完成时加上的知识点，算是拓展也算是拔高，所以解题思路全部都在此版块了，至于代码并没有展开，之后会在做题总结中写。

1.  了解如何在二叉搜索树中进行搜索、插入或删除;
    
    > 1.  如果目标值等于节点的值，则返回节点；
    > 2.  如果目标值小于节点的值，则继续在左子树中搜索；
    > 3.  如果目标值大于节点的值，则继续在右子树中搜索。
2.  在二叉搜索树中运用递归或迭代的方法，进行搜索、插入和删除操作;
    
    > 1.  根据节点值与目标节点值的关系，搜索左子树或右子树；
    > 2.  重复步骤 1 直到到达外部节点；
    > 3.  根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。
    
    > 1.  如果目标节点没有子节点，我们可以直接移除该目标节点。
    > 2.  如果目标节只有一个子节点，我们可以用其子节点作为替换。
    > 3.  如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
3.  了解节点数量、树的高度和操作复杂度之间的关系。

> 二叉搜索树的有优点是，即便在最坏的情况下，也允许你在`O(h)`的时间复杂度内执行所有的搜索、插入、删除操作。

**二叉树的性质：**

1.  若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个节点。
2.  若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(k>=0)，2^k-1
    
    【前两条的性质直接通过等比求和公式和特例解决就可以知道】
3.  对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1 。
    
    【证明：①有n个节点的树，有n-1边②任意一棵二叉树的节点总数n=n0+n1+n2并且每个度为2的节点都对应两条边，所以n-1=n1+2\*n2=n0+n1+n2-1==>n0=n2+1】
4.  具有n个结点的完全二叉树的深度k为log(n+1)上取整
    
    【随便用两个树实验一下就可以，另外还可以写成logn+1向下取整】
5.  对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：
    
    若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点若2*i+1<n，左孩子序号：2*i+1，否则无左孩子  
    若2*i+2<n，右孩子序号：2*i+2，否则无右孩子
    
    即**满足题意的前提下，孩子节点编号为i，那么双亲结点序号就是(i-1)/2**
    
    **双亲结点编号为i，那么左孩子节点序号就是2*i+1,右孩子是2*i+2**
    
    > ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hfdGaayy-1665045381222)(F:\\typora插图\\image-20221005103050993.png)\]][img-hfdGaayy-1665045381222_F_typora_image-20221005103050993.png]  
    > 因为是偶数个节点，所以一定有一个度为1的节点所以
    > 
    > 2n=n1+n0+n2=1+n0+n2==>n0=n2+1==>2n=2\*n0==>n0=n

> ![在这里插入图片描述][b9b8a20fad1d44f2816212d3e2ee7ae9.png]  
> 奇数个节点的完全二叉树，那么767=n0+n2=2\*n0-1====>n0=768/2=384

> ![这里是引用][c1b6849bc75f4b47ad540ddbc047c0d5.png]log(531+1)=log(534)>log(521)=====>10

### 三、二叉树的存储、遍历及基本操作实现 ###

#### 二叉树的存储： ####

存储方式：顺序存储和类似于链表的链式存储  
二叉树既可以用链式存储，也可以用顺序存储，不同的类型的二叉树适合不同的存储方式；  
比如完全二叉树适合顺序存储，这样比较节省空间；普通的二叉树可以用链式存储.其中堆无论何时都是一棵完全二叉树。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉【存两个引用】和三叉【存三个引用】表示方式。本节中，多大多数题目都是使用链式存储来解决问题的。

// 孩子表示法 ,目前使用孩子表示法更多
    class Node {
         
        int val;
    	Node left; 
        Node right;
    }
    //不存在双向单向的问题，他有左右之分，是有次序的
    // 孩子双亲表示法 
    class Node {
         
        int val;
    	Node left;
        Node right;
    	Node parent; 
    }

#### 二叉树的遍历 ： ####

每个二叉树都是由根节点、左子树、右子树组成的，而每棵子树也是这样的定义的，定义是递归的，所以我们在实现遍历操作的时候最好采用递归的方法解决。

遍历定义：沿着某条搜索路线，依次对树中的而每个节点做只做一次访问。

但是在实现操作之前我们先进行一个例子讲解，因为初学者容易对这个顺序理解错误。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5xEPtCOs-1665045381224)(F:\\typora插图\\image-20221005105241358.png)\]][img-5xEPtCOs-1665045381224_F_typora_image-20221005105241358.png]

![> \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JIGkttdc-1665045381225)(F:\\typora插图\\image-20221005105906178.png)\]][_img-JIGkttdc-1665045381225_F_typora_image-20221005105906178.png]

> ![在这里插入图片描述][907b726b6f9149e6a93a93948fb5a744.gif_pic_center]

> 层序遍历
> 
> ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OfYun3kX-1665045381226)(F:\\typora插图\\image-20221005110010730.png)\]][img-OfYun3kX-1665045381226_F_typora_image-20221005110010730.png]

##### 1.前序遍历【根节点–>左子树–>右子树】 #####

public void preOrder(TreeNode root){
        
        if(root==null){
        
            return ;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    
    //不直接打印而是存储到一个list表中
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            if(root==null){
        
                return list;
            }
            list.add(root.val);
            List<Integer>leftTree=preorderTraversal(root.left);
            list.addAll(leftTree);
            List<Integer> rightTree=preorderTraversal(root.right);
            list.addAll(rightTree);
            return list;
        }
    }

##### 2.中序遍历【左子树–>根节点–>右子树】 #####

public void inOrder(TreeNode root){
        
        if(root==null){
        
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            if(root==null){
        
                return list;
            }
            List<Integer>leftTree=inorderTraversal(root.left);
            list.addAll(leftTree);
            list.add(root.val);
            List<Integer> rightTree=inorderTraversal(root.right);
            list.addAll(rightTree);
            return list;
        }
    }

##### 3.后序遍历【左子树–>右子树–>根节点】 #####

public void postOrder(TreeNode root){
        
        if(root==null){
        
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            if(root==null){
        
                return list;
            }
            List<Integer>leftTree=postorderTraversal(root.left);
            list.addAll(leftTree);
            List<Integer> rightTree= postorderTraversal(root.right);
            list.addAll(rightTree);
            list.add(root.val);
            return list;
        }
    }

##### 4.层序遍历 #####

void levelOrder1(TreeNode root){
        
        if(root==null){
        
            return ;
        }
        Queue<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
        
            TreeNode cur=qu.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
        
                qu.offer(cur.left);
            }
            if(cur.right!=null){
        
                qu.offer(cur.right);
            }
        }
    }

> ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S9SGqVHN-1665045381229)(F:\\typora插图\\image-20221005111329237.png)\]][img-S9SGqVHN-1665045381229_F_typora_image-20221005111329237.png]

#### 确定二叉树的一些小规律 ####

另外我们还可以总结出来一些**规律**：

1.  只给出一个遍历无法创建一棵二叉树。【可能存在两颗树的某个遍历是一样的】
2.  只给出前序和后序确定不了一棵唯一的二叉树。【前序和后序都是确定根节点的位置，无法确定左右子树的位置，中序遍历确定的是左右子树的位置】
3.  后序遍历最后一个节点一定是根节点，如果有右树，那么倒数第二个节点一定是右树的根；先序遍历的第一个节点一定是根节点。
4.  对于中序遍历，根的左边是左树，右边是右树
5.  对于先序遍历，根的左边是根/左树，右边是右树

### 四、TreeSet的介绍及常用方法介绍 ###

#### 二叉树的基本操作 ####

1.  获取树中节点的个数
2.  获取叶子节点的个数
3.  子问题思路-求叶子结点个数
4.  获取第K层节点的个数
5.  获取二叉树的高度
6.  检测值为value的元素是否存在
7.  层序遍历
8.  判断一棵树是不是完全二叉树

#### TreeSet方法源码 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I6wvJijc-1665045381230)(F:\\typora插图\\image-20221006160952278.png)\]][img-I6wvJijc-1665045381230_F_typora_image-20221006160952278.png]

#### 二叉树常用操作模拟 ####

public class MyTree {
        
        class TreeNode{
        
            public char val;
            public int val2;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(char val) {
        
                this.val = val;
            }
    
            public TreeNode(int val2) {
        
                this.val2 = val2;
            }
        }
        public TreeNode root;
        public void preOrder(TreeNode root){
        
            if(root==null){
        
                return ;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        public void inOrder(TreeNode root){
        
            if(root==null){
        
                return ;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
        public void postOrder(TreeNode root){
        
            if(root==null){
        
                return ;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }
        int size(TreeNode root){
        //2.递归（递推公式）
    
            if(root==null){
        
                return 0;
            }
            return size(root.left)+size(root.right)+1;
        }
    
        //叶子结点的个数
        //叶子结点的定义：左右子树为空算一个
        int getLeafNodeCount(TreeNode root){
        
            if(root==null){
        
                return 0;
            }
            if(root.left==null&&root.right==null){
        
                return 1;
            }
            return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
        }
        // 获取第K层节点的个数
        //算一层的依据，左子树和右子树取最大值结果再+1
        //左子树和右子树k-1层的个数
        int getKLevelNodeCount(TreeNode root,int k){
        
            if(root==null||k<0){
        
                return 0;
            }
            if(k==1){
        
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }
        // 获取二叉树的高度
        public int getHeight(TreeNode root){
        
            if(root==null){
        
                return 0;
            }
            return Math.max(getHeight(root.left),getHeight(root.right))+1;
        }
        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, int val){
        
            if(root==null){
        
                return null;
            }
            if(root.val==val){
        
                return root;
            }
            TreeNode leftTreeNode=find(root.left,val);
            if(leftTreeNode!=null){
        
                return leftTreeNode;
            }
            TreeNode rightTreeNode=find(root.right,val);
            if(rightTreeNode!=null){
        
                return rightTreeNode;
            }
            return null;
        }
        void levelOrder(TreeNode root){
        
            if(root==null){
        
                return ;
            }
            Queue<TreeNode> qu=new LinkedList<>();
            qu.offer(root);
            while(!qu.isEmpty()){
        
                TreeNode cur=qu.poll();
                System.out.print(cur.val+" ");
                if(cur.left!=null){
        
                    qu.offer(cur.left);
                }
                if(cur.right!=null){
        
                    qu.offer(cur.right);
                }
            }
        }
        public boolean isCompleteTree(TreeNode root){
        
            if(root==null){
        
                return true;
            }
            Queue<TreeNode> qu=new LinkedList<>();
            qu.offer(root);
            while(!qu.isEmpty()){
        
                List<Integer> tmp=new ArrayList<>();
                TreeNode cur=qu.poll();
                if(cur==null){
        
                    break;
                }
                qu.offer(cur.left);
                qu.offer(cur.right);
            }
            //第一个null值的时候出来，然后如果后边队列有还非null的值就不是，后边没有值/全部是null那么就是完全二叉树
            while(!qu.isEmpty()){
        
                if(qu.poll()!=null){
        
                    return false;
                }
            }
            return true;
        }
    }

[img-7e8D5fmb-1665045381213_F_typora_image-20221006154345905.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/5a8b763f641d4da2891f3995b184bfc8.png
[img-n3ALfpHt-1665045381215_F_typora_image-20221005100536652.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c31ca7d5d1bd4c738b533907d6d5250b.png
[img-JrWupRXu-1665045381217_F_typora_image-20221005101302349.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/26d378656ac1448cbbf52fcf6946e2ac.png
[img-CW7GZAvu-1665045381218_F_typora_image-20221005101050738.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b958548f105c438f98c8c903db764e80.png
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/38c99ffb69f14919b86d3ad9099e17c0.png
[img-hfdGaayy-1665045381222_F_typora_image-20221005103050993.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/efa6baaaff724208a40008fd7a230d10.png
[b9b8a20fad1d44f2816212d3e2ee7ae9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/997db4bef88d40319fc7e7d8e1f40dbf.png
[c1b6849bc75f4b47ad540ddbc047c0d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/34af17781dd84f22905c4e3bf800a7f3.png
[img-5xEPtCOs-1665045381224_F_typora_image-20221005105241358.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9cf6527f3ae64146bf577de65fc39a23.png
[_img-JIGkttdc-1665045381225_F_typora_image-20221005105906178.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/cbaf8cf9898b4423acfb92ba578849d8.png
[907b726b6f9149e6a93a93948fb5a744.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/6ee5faf49c914a20a250577d0d4b24eb.gif
[img-OfYun3kX-1665045381226_F_typora_image-20221005110010730.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/106e1b6ad1f544a39d59dc98be592f31.png
[img-S9SGqVHN-1665045381229_F_typora_image-20221005111329237.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/43909f9b67dc498c8902bb363266d725.png
[img-I6wvJijc-1665045381230_F_typora_image-20221006160952278.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/217df9419cac42169229cf138e9ac83c.png