数据结构之树型结构

    • 相关概念
    • 树的表示
    • 二叉树
      • 二叉树性质
      • 二叉树储存
    • 实现一颗二叉树
      • 创建
      • 遍历(前中后序)
      • 获取树中节点个数
      • 获取叶子节点个数
      • 获取第k层节点个数
      • 获取二叉树高度
      • 检测值为value元素是否存在
      • 层序遍历(需要队列来实现)
      • 判断是否为完全二叉树(需要队列来实现)

相关概念

在这里插入图片描述
重点概念:后续学习将会反反复复出现
在这里插入图片描述

对我们当前学习稍微不重要:

在这里插入图片描述

树的表示

树有很多种表示方式,如:双亲表示法,孩子表示法、孩子双亲表示法(AVL树、红黑树、B树会用到)、孩子兄弟表示法等等。我们了解一下孩子兄弟表示法:
在这里插入图片描述
代码表示:

class Node{
	int value;//我们当前学习就是简简单单的存个int数字
	Node firstChild;
	Node nextNorther;

}

二叉树

二叉树:每一个节点的度小于等于2;其实就是每一个节点的孩子个数不超过两个。二叉树的有次序是指你把右子树放左边画出来,结果就是两个不同的树
任意二叉树都是由以下的情况组合的:
在这里插入图片描述
满二叉树:每层的结点数都达到最大值;如果层数是k;满二叉树的节点个数为2^k-1

完全二叉树:你按左右到上下编号1-n一定是连续的
在这里插入图片描述

二叉树性质

前提:规定第一层是根节点的二叉树
1:第i层最多节点个数:2^(i-1)
2:深度为k;总节点个数最多是2^k-1 (完全二叉树的情况)

3:非常重要;任意的二叉树;叶子节点个数比度为2的节点个数多一个(度为0就是叶子,不涉及到度为1的节点)
n0=n2+1 (如果要把n1也扯上关系;使用n-1=n00+n11+n2*2;n是总节点个数;解释:一颗n个节点的树有N-1条边;而叶子节点不产生边;度为1的节点只产生一条边;度为2的节点产生两条边)
比如有4层:
其实就是;2的4次方等于2的3次方+2都平方+2的1次方+2的0次方+1。
题目:
某二叉树共有399个结点,其中有199个度为2的结点,则该二叉树中的叶子结点数为()
A不存在这样的二叉树
B200
C198
D199

4:具有n个结点的完全二叉树的深度k为log(n+1)向上取整
不受到你最后层节点个数影响,最后层一个跟2的n-1个是一样,因为用最大节点个数推导出来的
5:对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点若2i+1<n,左孩子序号:2i+1,否则无左孩子
若2i+2<n,右孩子序号:2i+2,否则无右孩子
注意:完全二叉树度为1的节点要么是1个,要么是0个。奇数个节点就没有度为1的节点,偶数个节点就有一个度为1的节点。如果题目告诉你2n个节点;那就说明有度为1的节点

二叉树储存

在这里插入图片描述
如何遍历:
先序:根—>左子树---->右子树(这个比较容易理解)
中序:左子树—>根—>右子树(先访问左子树,然后你左子树又得按照中序进行)
后序:左子树–>右子树—>根

实现一颗二叉树

创建

//创建一颗树
class  tree{
    //树的节点,还是内部类实现,类似链表
    class Listnode{
        //一个节点包含三个域
        char val;
        Listnode left;//左边
        Listnode right;//右边

        public Listnode(char val) {
            this.val = val;
        }
    }
    public Listnode create(){
        //先把节点和值创建好,然后再绑关系
        Listnode A=new Listnode('A');
        Listnode B=new Listnode('B');
        Listnode C=new Listnode('C');
        Listnode D=new Listnode('D');
        Listnode E=new Listnode('E');
        Listnode F=new Listnode('F');
        Listnode G=new Listnode('G');
        //这里的B和C是节点
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;

        return A;//返回根节点
    }

遍历(前中后序)

前序:

   public void print1(Listnode root){
        if(root==null) {
            return ;
        }
        System.out.println(root.val);
        print1(root.left);
        print1(root.right);

    }

中序:这次我们就不打印;遍历把值存在顺序表里

    public List<Character> print2(Listnode root){
        List<Character> list=new ArrayList<>();
        if(root==null)
        {
            return list;
        }
        //System.out.println(root.val);
        list.add(root.val);
        print2(root.left);
        print2(root.right);
        return list;
    }

后序:

public List<Character> print3(Listnode root){
    List<Character> ret=new ArrayList<>();
    if(root==null)
    {
        return ret;
    }
    //System.out.println(root.val);
    ret.add(root.val);//先把头放进去,然后左边放一个表,右边放一个表,最后放到ret
    List<Character> s=print3(root.left);
               ret.addAll(s);
    List<Character> s1=print3(root.right);
    ret.addAll(s1);
    return ret;
}

获取树中节点个数

//获取树中节点的个数
    int num=0;
    public int size(Listnode root){
        //遍历计数器
        if(root==null) {
            return 0;
        }
        num++;
        size(root.left);
        size(root.right);
        return num;
    }
    //子问题计数
    public int size1(Listnode root){
        if(root==null) {
            return 0;
        }
        int tmp =size1(root.left)+size1(root.right)+1;//(把走到每个节点都分为左边、右边和它自己)
        return tmp;
    }

获取叶子节点个数

   // 获取叶子节点的个数
    int ret3=0;
     public  void getLeafNodeCount(Listnode root){
//自己为空,肯定就结束了
    if(root==null){
        return ;
    }
    //如果左边和右边同时为空就计数
         if(root.left==null&&root.right==null){
             ret3++;
         }
       getLeafNodeCount(root.left);
       getLeafNodeCount(root.right);

     }
    // 子问题思路-求叶子结点个数
    public  int getLeafNodeCount1(Listnode root){
//自己为空,肯定就结束了
        if(root==null){
            return 0;
        }
        //如果左边和右边同时为空就计数
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);

    }

获取第k层节点个数

   // 获取第K层节点的个数,直接子问题
  public  int getKLevelNodeCount(Listnode root,int k){
//我们之前不是求了一棵树节点个数吗;假设我要求k层,在k-1的左右子树的和
	if(root==null||k<=0) {
	      return -1;
	}
	if(k==1){//这时候条件就不再是root.left==null&&root.right==null;而是k-1层的孩子节点我都要计算
	    return 1;
	}
	int tmp=getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);

	return tmp;
    }



获取二叉树高度

非常巧妙:递归的结束root==null;返回上一级到叶子节点;发现height1>height2不成立;叶子节点的右边+1;如果是root.left遍历下的就返回给这里的值。画个图就好理解

  // 获取二叉树的高度
    public int getHeight(Listnode root) {
        if(root==null){
            return 0;
        }
        int height1=  getHeight(root.left);
        int height2= getHeight(root.right);
        if (height1>height2){
            return height1+1;//加1是关键,每结束一层+1
        }
        else
            return height2+1;
    }

在这里插入图片描述

检测值为value元素是否存在

   // 检测值为value的元素是否存在
   public Listnode find(Listnode root, int val) {
       if (root == null) {
           return null;
       }
       if (root.val == val) {

           return root;
       }
       find(root.left, val);//这里应该把find(root.left,val)存到ret里,避免下面用这个又要重复再递归一次
       if (find(root.left, val).val == val) {
           return root;
       }     //如果我在左边找到就不去右边

       //如果我在右边找到就直接结束,如果都没找到
       find(root.right, val);
       if (find(root.right, val).val == val) {
           return root;
       }
       return null;

       
   }

层序遍历(需要队列来实现)

因为二叉树;没法按这种顺序来遍历;就得依靠别的数据结构
在这里插入图片描述
这样子它的打印顺序就是从左到右;画图分析好
在这里插入图片描述

判断是否为完全二叉树(需要队列来实现)

队列;逻辑:按层次遍历弹出,把Null也放入队列里,当弹出Null的时候发现队列全为Null,就说明是完全二叉树
。不全为null就不是完全二叉树。

   // 判断一棵树是不是完全二叉树   ,这题逻辑还是非常清晰
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()) {
            TreeNode cur = qu.poll();
            if(cur != null) {
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else {
                break;
            }
        }
        //判断队列剩下的值 是否有 非null的数据
        while (!qu.isEmpty()) {
            TreeNode pop = qu.poll();
            if(pop != null) {
                return false;
            }
        }
        return true;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/95060.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

高职教育应对ChatGPT应用的策略

一、完善顶层设计&#xff0c;提升技术水平 在推广ChatGPT平台的过程中&#xff0c;高职院校需要关注技术本身的问题。这就需要在国家和地方政府的引导下&#xff0c;引入更完善的技术顶层设计&#xff0c;提高人工智能在高职教育中的运用水平。具体来说&#xff0c;一方面需要…

C# 多线程交替按照指定顺序执行

1.关于AutoResetEvent和ManualResetEvent的区别解释如下&#xff1a; AutoResetEvent和ManualResetEvent是.NET中的两个线程同步类。它们之间的主要区别在于其释放信号的方式以及对等待线程的影响。 AutoResetEvent的作用是在等待的线程被信号唤醒后&#xff0c;将信号自动重…

Kubernetes(k8s)当中安装并使用ingress暴露应用

Kubernetes当中安装并使用ingress暴露应用 为什么需要Ingress前期准备集群准备LoadBalancer准备 安装Ingress-Nginx下载地址v1.3.1v1.8.1 修改文件v1.3.1v1.8.1修改ingress服务类型配置 执行安装 部署应用通过ingress-nginx暴露应用部署ingress的yaml文件v1.3.1v1.8.1 为什么需…

前端加springboot实现Web Socket连接通讯以及测试流程(包括后端实现心跳检测)

【2023】前端加springboot实现Web Socket连接通讯&#xff08;包括后端实现心跳检测&#xff09; 前言一、Web Socket 简绍1 为什么用 websocket&#xff1f; 二、代码实现1、前端&#xff08;html&#xff09;1.1、无前端向后端发送消息1.2、有前端向后端发送消息 2、后端具体…

【Android】AES解密抛出异常Cipher functions:OPENSSL_internal:WRONG_FINAL_BLOCK_LENGTH

Java使用AES加密的时候没得问题&#xff0c;但是在解密的时候就出错了&#xff0c;一起来找找原因吧。 首先&#xff0c;Java运行的代码如下&#xff0c;使用AES加解密 Cipher cipher Cipher.getInstance("AES/CBC/NOPadding"); //...主要问题 可调试运行控制台抛…

自动泊车的自动驾驶控制算法

1. 自动泊车系统 自动泊车系统(AutomatedParkingASSiSt,APA)利用车辆搭载的传感器感知车辆周边环境,扫描满足当前车辆停放的障碍物空间车位或线车位,并通过人机交互(HumanMachine Interface,HMI)获取驾驶员对目标车位的选择或自动确定目标车位,自动规划泊车路径,通过控制器向车…

Icon设计神器!这5个软件一定要试试

在界面设计中&#xff0c;Icon既可以为用户指明用途&#xff0c;又可以提升界面设计的质感&#xff0c;可以说是一种必不可少的设计素材。而市面上可以制作的Icon的设计软件也十分丰富&#xff0c;今天本文将选出了5个好用的与大家分享&#xff0c;它们不仅功能强大&#xff0c…

全国首台!浙江机器人产业集团发布垂起固定翼无人机-机器人自动换电机巢

展示突破性创新技术&#xff0c;共话行业发展趋势。8月25日&#xff0c;全国首台垂起固定翼无人机-机器人自动换电机巢新品发布会暨“科创中国宁波”无人机产业趋势分享会在余姚市机器人小镇成功举行。 本次活动在宁波市科学技术协会、余姚市科学技术协会指导下&#xff0c;由浙…

无涯教程-分类算法 - 逻辑回归

逻辑回归是一种监督学习分类算法&#xff0c;用于预测目标变量的概率&#xff0c;目标或因变量的性质是二分法&#xff0c;这意味着将只有两种可能的类。 简而言之&#xff0c;因变量本质上是二进制的&#xff0c;其数据编码为1(代表成功/是)或0(代表失败/否)。 在数学上&…

Ubuntu【系统环境下】【编译安装OpenCV】【C++调用系统opencv库】

Ubuntu【系统环境下】【编译安装OpenCV】【C调用系统opencv库】 前言&#xff1a; 本人需要用C写代码&#xff0c;调用OpenCV库&#xff0c;且要求OpenCV版本号大于4.1.0 由于使用的是18.04的版本&#xff0c;所以apt安装OpenCV的版本始终是3.2.0&#xff0c;非常拉胯&#…

【持续更新中】QAGroup1

OVERVIEW Q&AGroup1一、语言基础1.C语言&#xff08;1&#xff09;含参数的宏与函数的不同点&#xff08;2&#xff09;sizeof与strlen的区别&#xff08;3&#xff09;大/小端&#xff08;4&#xff09;strcpy与memcpy的区别&#xff08;5&#xff09;extern与static的区别…

登高不系安全带自动识别

登高不系安全带自动识别采用yolov8深度学习算法框架模型&#xff0c;登高不系安全带自动识别能够自动检测和识别登高作业人员是否佩戴安全带&#xff0c;过滤其他类似物体的干扰。登高不系安全带自动识别发现有人员未佩戴安全带&#xff0c;将立即触发预警。根据YOLO的设计&…

面试题-React(七):React组件通信

在React开发中&#xff0c;组件通信是一个核心概念&#xff0c;它使得不同组件能够协同工作&#xff0c;实现更复杂的交互和数据传递。常见的组件通信方式&#xff1a;父传子和子传父 一、父传子通信方式 父组件向子组件传递数据是React中最常见的一种通信方式。这种方式适用…

适配小程序隐私保护指引设置

由于小程序发布了一个公告&#xff0c;那么接下来就是怎么改简单的问题了。毕竟不太想大的改动历史上的代码。尽量简单的适配隐私策略就可以了。 整体思路也是参考现在App普遍的启动就让用户同意隐私策略&#xff0c;不同意不让用&#xff0c;同意了之后才能够继续使用。 公告…

ELK高级搜索(二)

文章目录 7&#xff0e;Java api 文档管理7.1 es技术特点7.2 获取数据7.3 文档查询7.4 文档新增7.5 文档修改7.6 文档删除7.7 文档bulk 8&#xff0e;图解es内部机制8.1 es分布式基础8.2 分片shard、副本replica8.3 单node环境创建index8.4 多node环境replica shard8.5 横向扩容…

数据结构之哈希

哈希 1. 哈希概念2. 哈希冲突3. 哈希冲突解决3.1 哈希表的闭散列3.2 哈希表的开散列 4. 哈希的应用4.1 位图4.2 布隆过滤器 哈希&#xff08;Hash&#xff09;是一种将任意长度的二进制明文映射为较短的二进制串的算法。它是一种重要的存储方式&#xff0c;也是一种常见的检索方…

【NLP的python库(01/4) 】: NLTK

一、说明 NLTK是一个复杂的库。自 2009 年以来不断发展&#xff0c;它支持所有经典的 NLP 任务&#xff0c;从标记化、词干提取、词性标记&#xff0c;包括语义索引和依赖关系解析。它还具有一组丰富的附加功能&#xff0c;例如内置语料库&#xff0c;NLP任务的不同模型以及与S…

Lua基础知识

文章目录 1. Lua简介1.1 设计目的&#xff1a;1.2 特性1.3 应用场景 2. Lua脚本学习2.1 安装2.2 lua操作2.3 lua案例 学习lua主要是为了后续做高性能缓存架构所准备的基础技术。可以先了解下基础&#xff0c;在实际使用时&#xff0c;再查缺补漏。 1. Lua简介 Lua 是一种轻量小…

【JavaWeb 专题】15个最经典的JavaWeb面试题

文章目录 HTTP长连接和短连接HTTP/1.1 与 HTTP/1.0 的区别可扩展性缓存带宽优化长连接消息传递Host 头域错误提示 AjaxAjax 的优势&#xff1a; JSP 和 servlet 有什么区别&#xff1f;定义区别 JSP 的9大内置对象及作用JSP 的 4 种作用域&#xff1f;session 和 cookie 有什么…

实用的面试经验分享:程序员们谈论他们的面试历程

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…