当前位置：首页 > news >正文

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

news 来源：原创 2024/5/17 12:26:48

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

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

特点：

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]$

特殊的二叉树及性质

满二叉树：

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

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

完全二叉树：

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

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

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

二叉搜索树（BST）

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

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

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

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

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

二叉树的性质：

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个节点。
若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(k>=0)，2^k-1

【前两条的性质直接通过等比求和公式和特例解决就可以知道】
对任何一棵二叉树, 如果其叶结点个数为 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】
具有n个结点的完全二叉树的深度k为log(n+1)上取整

【随便用两个树实验一下就可以，另外还可以写成logn+1向下取整】
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子

即满足题意的前提下，孩子节点编号为i，那么双亲结点序号就是(i-1)/2

双亲结点编号为i，那么左孩子节点序号就是2i+1,右孩子是2i+2

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hfdGaayy-1665045381222)(F:\typora插图\image-20221005103050993.png)]$
因为是偶数个节点，所以一定有一个度为1的节点所以

2n=n1+n0+n2=1+n0+n2==>n0=n2+1==>2n=2*n0==>n0=n

奇数个节点的完全二叉树，那么767=n0+n2=2*n0-1====>n0=768/2=384

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-JIGkttdc-1665045381225)(F:\typora插图\image-20221005105906178.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)]$

确定二叉树的一些小规律

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

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

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

二叉树的基本操作

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

TreeSet方法源码

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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;
    }
}