• 能带你起飞的【数据结构】成王第八篇:二叉树

    前言

    树形结构

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

    特点:

    1.有一个特殊的节点，称为根节点，根节点没有前驱节点,A就是根节点

    2.除根节点外，其余节点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继

    B C D E......都是一个集合.

    B就是一棵子树,它的前驱就是A

    注意:树形结构中,子树之间不能有交集,否则就是不是树形结构

    好比划红线的地方

    3.树是递归定义的。

    节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

    最大的深度才是树的高度 如上图:A深度是1,E深度是2,J深度是3,Q深度是4

    树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

    叶子节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点

    双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

    孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

    根结点：一棵树中，没有双亲结点的结点；如上图：A

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

    树的表现形式

     树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

    A是val值

    child是第一个孩子的引用,第一个孩子是B,所以引用了B这个节点

    Node nextBrother下一个兄弟:因为A是根节点,没有兄弟,所以brother的值是null

    到B之后,B的第一个孩子是D,兄弟是C,假设C没有兄弟,brother的值也是null

    依次往下类推

    树的应用

    文件系统管理(目录和文件)

    二叉树

    一棵二叉树是结点的一个有限集合，该集合:

    1.或者为空

    2.或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

    二叉树的每个节点要么有0个孩子,要么有1个孩子,要么有两个孩子 <=2

    一棵树,如果是二叉树,那么他的每棵子树都是二叉树

    二叉树不存在度大于2的截断

    二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

    两种特殊的二叉树 

    1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2的k次方减1 ，则它就是满二叉树。

    2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

    二叉树的性质 

    1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有

    2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是

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

    1和2比较简单,等比数列就可以推导出来

    我们来推导一下公式3,

    假设二叉树有N个节点,一棵二叉树,要么n0(表示叶子节点),要么n1,要N2

    所以:N = n0+n1+n2

    一个有N个节点的树,有N-1条边

    边的总数等于:

    度为0的节点,产生0条边

    度为1的节点,产生n1条边

    度为2的节点,产生n2条边

    N-1 = n1 + 2*n2

    n0+n1+n2 = n1 + 2*n2 -1

    n0 = n2 + 1

    得出结论:任何一棵二叉树,叶子节点比度为2的节点多一个

    4. 具有n个结点的完全二叉树的深度k为 上取整

    下图是向上取整

    我们看一个题:

    在具有2n个节点的完全二叉树中,叶子结点个数为()

    A:n

    B:n+1

    C:n-1

    D:n/2

    选A

    根据我们上面提出的结论:任何一棵二叉树,叶子节点比度为2的节点多一个

    5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

    若i>0，双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

    解释:
     

    假设孩子节点的下标是i,那么双亲节点的下标是:

    假设Ii为5,父亲节点为2,假设i为6,父亲节点为2

    (i-1)/2

    (5-1)/2 = 2

    (6-1)/2 = 2

    若2i+1<n,左孩子序号:2i+1,否则无左孩子

    若2i+2<n,右孩子序号:2i+2,否则无右孩子

    解释:

    假设父亲节点的下标是i

    左孩子:2i + 1

    右孩子:2i + 2

    二叉树的存储 

    二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

    二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

    二叉:孩子表示法

    三叉:孩子双亲表示法

    二叉树的创建 

    前提:二叉树的创建是一个非常复杂的过程,前面的知识还不够让大家了解二叉树,所以现在先创建一个二叉树,这种创建方式只是我们前期使用,比较简单,不是正确的或者是常用的创建方式.

    假设创建这棵树

    1. class BTNode{
    2.     public char val;
    3.     public BTNode left;//左孩子的引用
    4.     public BTNode right;//右孩子的引用
    5.  
    6.     public BTNode(char val){
    7.         this.val = val;
    8.     }
    9. }
    10. public class BinaryTree {
    11.     public BTNode root;//根节点是属于二叉树的根,不是属于节点的根
    12.  
    13.     public BTNode createTree(){
    14.         BTNode A = new BTNode('A');
    15.         BTNode B = new BTNode('B');
    16.         BTNode C = new BTNode('C');
    17.         BTNode D = new BTNode('D');
    18.         BTNode E = new BTNode('E');
    19.         BTNode F = new BTNode('F');
    20.         BTNode G = new BTNode('G');
    21.         BTNode H = new BTNode('H');
    22.         A.left = B;
    23.         A.right = C;
    24.         B.left = D;
    25.         B.right = E;
    26.         C.left = F;
    27.         C.right = G;
    28.         E.right = H;
    29.         return A;
    30.  
    31.     }
    32. }

    这是一个简单的创建二叉树的方式

    二叉树的遍历

    二叉树的遍历,重点 》所有的二叉树相关的题目，基本都需要通过某种遍历来去解题的。

    1.前序遍历（又叫先根遍历）

    遇到根先打印，再打印左子树，在打印右子树

     2.中序遍历

    先打印左子树，再打印根，再打印右子树

    3.后序遍历

    先打印左子树，再打印右子树，再打印根

    写一个前序遍历的代码：

    1.   //前序遍历
    2.     public void preOrder(BTNode root){
    3.         if(root == null){
    4.             return;
    5.         }
    6.         System.out.println(root.val+ " ");
    7.         preOrder(root.left);
    8.         preOrder(root.right);
    9.     }

     递归方式

    二叉树的题天生就是用递归来写的,90%

    打印结果:

    我们来看一个题:

    144. 二叉树的前序遍历 - 力扣（LeetCode）

    第一种代码写法:遍历思路

    1. class Solution {
    2.     public List<Integer> preorderTraversal(TreeNode root) {
    3.         List<Integer> list = new LinkedList<>();
    4.         pre(list,root);
    5.         return list;
    7.     }
    8.     public void pre(List<Integer> list,TreeNode root){
    9.             if(root != null){
    10.             list.add(root.val);
    11.             pre(list,root.left);
    12.             pre(list,root.right);
    13.             }
    14.             
    15.         }
    16. }

    第二种解法:遍历思路

    1. class Solution {
    2.    List<Integer> list = new ArrayList<>();
    3.     public List<Integer> preorderTraversal(TreeNode root) {
    4.         
    5.        if(root == null){
    6.            return list;
    7.        }
    8.        list.add(root.val);
    9.        preorderTraversal(root.left);
    10.        preorderTraversal(root.right);
    11.         return list;
    12.     }           
    13.         
    14. }

    第三种解法:子问题思路

    1. class Solution {
    2.   
    3.     public List<Integer> preorderTraversal(TreeNode root) {
    4.          List<Integer> list = new ArrayList<>();
    5.        if(root == null){
    6.            return list;
    7.        }
    8.        list.add(root.val);
    9.     List<Integer> leftTree = preorderTraversal(root.left);
    10.        list.addAll(leftTree);
    11.     List<Integer> rightTree = preorderTraversal(root.right);
    12.     list.addAll(rightTree);
    13.         return list;
    14.     }           
    15.         
    16. }

    未完,待续......

  • 相关阅读:
    [VIM] MiniBufExplorer插件
    MySQL 基础笔记（2）
    你知道在Linux终端中“＞“和“＞＞“之间的区别吗？
    2022杭电多校第一场题解
    051校园短期闲置资源置换平台
    JDK19虚拟线程初探（三）
    【中鸡前端+Vue面试精选】
    不使用加法计算两个数的和
    推送多架构镜像到同一仓库
    使用MediatR和FluentValidation实现CQRS应用程序的数据验证
  • 原文地址：https://blog.csdn.net/m0_64397675/article/details/125398479