初识树型结构与二叉树

1. 树型结构

        树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树(它是根朝上,而叶朝下的),其物理结构如下图所示:

                             

        其中树形结构具有以下的特点:

        1、有一个特殊的结点,称为根结点,根结点没有前驱结点

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

        3、树是递归定义的

        4、树形结构中,子树之间不能有交集,否则就不是树形结构  

        5、一个有n个节点的树,它有n-1条边;

1.1 关于树的关键词

        下面的一些列重要关键词汇的介绍是针对下图树来讲解的:

           

一级词汇(重点理解):

1、结点的度(节点的分支一个结点含有子树的个数称为该结点的度; 如上图:A的度为6 

2、树的度(分支最多的那个节点的分支数:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6

3、叶子结点或终端结点(没有分支的节点:度为0的结点称为叶结点; 如上图:B、C、H、I...等节点为叶结点

4、双亲结点或父结点有分支的节点):若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点

5、孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点

6、根结点(最顶头的节点:一棵树中,没有双亲结点的结点;如上图:A

7、结点的层次从上到下数,该节点在第几行):从根开始定义起,根为第1层,根的子结点为第2层,以此类推

二级词汇(了解即可)

1、非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G...等节点为分支结点

2、兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点

3、兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点

4、堂兄弟结点 :双亲在同一层的结点互为堂兄弟;如上图: H 、 I 互为兄弟结点
5、结点的祖先 :从根到该结点所经分支上的所有结点;如上图: A 是所有结点的祖先
6、子孙 :以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是 A 的子孙
7、森林 :由 m ( m>=0 )棵互不相交的树组成的集合称为森林

1.2 树的表示形式  

        树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦,实际中树有很多种表示方式,如:双亲表示法, 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。

        这里通过代码简单的了解其中最常用的孩子兄弟表示法;

class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}

        下图是孩子兄弟表示法的树结构图解:

        如上图所示,孩子兄弟表示法主要通过child域(存放该节点的子节点的地址)和brother域(存放该节点兄弟节点的地址)来完成整个树构成;

2. 二叉树

        一棵二叉树是关于结点的一个有限集合,该集合的特点:

        1. 或者为空

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

                       

        如上图就是将一个二叉树分解成概念中的节点的有限集合的形式(左子树<--根节点-->右子树),从上图可以看出:

        1. 二叉树不中结点的分支最多就是2个分支;

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

2.1 特殊的二叉树 

        1. 满二叉树(除了叶子节点,其余的节点都有两个分支) : 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树 。也就是说,如果一棵二叉树的层数为 K,且结点总数是(2^K)-1 ,则它就是满二叉树 ,如下图就是满二叉树;

                                 
        2. 完全二叉树 : 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于所有的节点按照二叉树的规则,依据从上到下,从左到右,依次排序的准则排序的二叉树, 要注意的是满二叉树是一种特殊的完全二叉树,如下图就是完全二叉树;

                            

2.2 二叉树的性质

1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (2^i-1)  (i>0)个结点

        //已知第几层------> 计算该层节点个数

2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是(2^K)-1 (k>=0)

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

推导过程如下所示:

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

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

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

5.1重要的两个小结论:

3.二叉树例题讲解

1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )

A 不存在这样的二叉树

B 200

C 198

D 199

        由性质3可得: 对任何一棵二叉树 , 如果其叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有n0=n2+1------->399=n0+n2-------->399=n0+n0-1----->n0=200

或者---->
                n0=199+1为200;------>B

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

A n

B n+1

C n-1

D n/2

        考虑是否存在最后一个节点只有一个分支的节点,图解如下图所示:

 由n0 = n2 +1可得:

左图:2n = n0 + 1 +n0-1------------->n0 = n---------->A;

右图:2n = n0 +n0-1------------------->n0=(2n+1)/2;

 3.一个具有767个节点的完全二叉树,其叶子节点个数为()

A 383

B 384

C 385

D 386

由n=n0+n1+n0-1--------->768=2n0+n1------>因为n1只能为1------>不满足题意,令n1 =0----->n0=768/2 =384; 

 4.一棵完全二叉树的节点数为531个,那么这棵树的高度为( )

A 11

B 10

C 8

D 12

 

性质4:具有n个结点的完全二叉树的深度k为: 

注意:向上取整

512=2^9<2^10;

故令h =10;

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

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

相关文章

docker部署elasticsearch8.x

docker部署elasticsearch8.x 提示1 注意版本差别1.1 docker修改配置1.1.2 docker使用vim报命令不存在的解决办法1.1.3 docker 容器内报错 E: List directory /var/lib/apt/lists/partial is missing. - Acquire ( : No such file or directory) 或者其他权限 PermissionError: …

鸿蒙HarmonyOS4.0开发应用学习笔记

黑马程序员鸿蒙4.0视频学习笔记&#xff0c;供自己回顾使用。1.安装开发工具DevEco Studio 鸿蒙harmony开发文档指南 DevEco Studio下载地址 选择或者安装环境 选择和下载SDK 安装总览 编辑器界面 2.TypeScript语法 2.1变量声明 //string 、number、boolean、any、u…

Linux指令学习

目录 1.ls指令 2.pwd命令 3.cd 指令 4. touch指令 5.mkdir指令 6.rmdir指令 && rm 指令 7.man指令 8.cp指令 9.mv指令 10.cat指令 11.more指令 12.less指令 13.head指令 14.find指令&#xff1a; -name 15.grep指令 16.zip/unzip指令&#xff1a; 17.tar…

JavaWeb(十)

一、JavaWeb概述 Web&#xff1a;全球广域网&#xff0c;也称为万维网(www)&#xff0c;能够通过浏览器访问的网站。 JavaWeb&#xff1a;使用 Java技术进行web互联网开发。 二、JavaWeb 技术栈 2.1、B/S 架构 B/S 架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器…

看图学源码—Java集合 之 ArrayList 源码分析

ArrayList public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}实现的接口 Serializable 类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态 …

区块链密码学:基础知识、应用与未来发展

一、引言 区块链技术&#xff0c;作为一种分布式、去中心化的数据管理方式&#xff0c;密码学在其安全性和可靠性方面发挥着至关重要的作用。本文将详细介绍区块链密码学的基础知识、应用以及未来发展趋势。 二、区块链密码学基础知识 区块链密码学是区块链技术的核心组成部分…

02 CSS基础入门

文章目录 一、CSS介绍1. 简介2. 相关网站3. HTML引入方式 二、选择器1. 标签选择器2. 类选择器3. ID选择器4. 群组选择器 四、样式1. 字体样式2. 文本样式3. 边框样式4. 表格样式 五、模型和布局1. 盒子模型2. 网页布局 一、CSS介绍 1. 简介 CSS主要用于控制网页的外观&#…

联通宽带+老毛子Padavan固件 开启IP v6

联通宽带开启IP v6 参考&#xff1a; 联通宽带开启 IPV6 的方法_联通ipv6怎么开通-CSDN博客 个人宽带如何开启IPv6网络访问 - 知乎 (zhihu.com) 首先&#xff0c;你要确定当前你所在的地区运营商已经开通了IPV6&#xff0c;可以使用手机流量 IP查询(ipw.cn) | IPv6测试 | IPv…

ELK 日志解决方案

ELK 是目前最流行的集中式日志解决方案&#xff0c;提供了对日志收集、存储、展示等一站式的解决方案。 ELK 分别指 Elasticsearch、Logstash、Kibana。 Elasticsearch&#xff1a;分布式数据搜索引擎&#xff0c;基于 Apache Lucene 实现&#xff0c;可集群&#xff0c;提供…

【FPGA图像处理实战】- VGA接口与时序详解

VGA接口是一个很有历史的接口&#xff0c;全称为Video Graphics Array&#xff08;VGA&#xff09;视频图形阵列&#xff0c;是IBM公司在1987年随着PS/2一起推出的使用模拟信号的一种视频传输标准。 时至今日&#xff0c;这个接口依然还在大量使用&#xff0c;因为这个接口具有…

【PTA-C语言】编程练习4 - 数组Ⅰ

如果代码存在问题&#xff0c;麻烦大家指正 ~ ~有帮助麻烦点个赞 ~ ~ 编程练习4 - 数组Ⅰ&#xff08;1~7&#xff09; 7-1 评委打分&#xff08;分数 10&#xff09;7-2 组合数的和&#xff08;分数 10&#xff09;7-3 找不同&#xff08;分数 15&#xff09;7-4 利用二分查找…

Linux shell编程学习笔记33:type 命令

目录 0 引言1 type 命令的功能和格式 1.1 type命令的功能1.2 type 命令的格式2 type命令用法实例 2.1用type命令查看shell内置命令&#xff08;以echo命令为例&#xff09;2.2 用type命令查看别名&#xff08;以ls命令为例&#xff09;2.3 用type命令同时查看shell内置命令和别…

Kubernetes实战(八)-防止k8s namespace被误删除

1 背景 运维新同学在预发环境操作删除pod的时候&#xff0c;不知道什么原因把kubectl delete pod命令敲成了kubectl delete ns pre把预发环境删了&#xff0c;几十个模块&#xff0c;将近一个小时才恢复。幸亏是测试环境啊&#xff0c;如果是生产可以可以跑路了。 2 解决方案…

Redis核心知识点总结

1.Redis介绍 Redis 是 NoSQL&#xff0c;但是可处理 1 秒 10w 的并发&#xff08;数据都在内存中&#xff09; 使用 java 对 redis 进行操作类似 jdbc 接口标准对 mysql&#xff0c;有各类实现他的实现类&#xff0c;我们常用的是 druid 其中对 redis&#xff0c;我们通常用 J…

深信服技术认证“SCSA-S”划重点:XSS漏洞

为帮助大家更加系统化地学习网络安全知识&#xff0c;以及更高效地通过深信服安全服务认证工程师考核&#xff0c;深信服特别推出“SCSA-S认证备考秘笈”共十期内容&#xff0c;“考试重点”内容框架&#xff0c;帮助大家快速get重点知识~ 划重点来啦 *点击图片放大展示 深信服…

彻底解决公网ip无法访问服务器的问题

用服务器的公网ip访问突然提示页面无法访问了&#xff0c;之前还是ok的&#xff1a; 解决方案&#xff1a; 步骤1. 检查云服务器的安全组规则是否有添加80端口映射&#xff0c;如果没有需要手动添加&#xff0c;否则不能使用公网访问&#xff0c;检查了一下是有的&#xff1…

STM32 定时器总结

缩写 ARR: Auto-Reload Register&#xff08;保存定时器的计数范围&#xff09; PSC: Prescaler register&#xff08;预分频器寄存器&#xff0c;根据设置的分频因子N&#xff0c;计数N个定时器时钟脉冲后&#xff0c;产生一个CNT计数&#xff0c;以此实现分频功能&#xff0…

Python中函数添加超时时间,Python中signal使用

from time import time, sleepimport signal# 模拟要删除5条数据,中间有超时的i 5# 超时后执行的方法def timeout_handler(signal, frame):# 引发异常raise TimeoutError("删除第" str(i) "条,超时!")# 或者执行其他操作,不往外抛异常(超时的函数不会被…

nodejs+vue+微信小程序+python+PHP的Sd球鞋销售平台的设计与实现-计算机毕业设计推荐

此网站系统的开发方式和信息管理方式&#xff0c;借鉴前人设计的信息和研发。以网站商品信息为主&#xff0c;购物商品为核心功能来进行设计和研发&#xff0c;把网站信息和技术整合&#xff0c;开发出一套Sd球鞋销售平台。用目前现有的新技术进行系统开发&#xff0c;   目…

外包干了3个月,技术倒退2年。。。

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…