还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

这篇具有很好参考价值的文章主要介绍了还在担心期末挂科吗? 期末必备复习资料-----“树“的概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:记录期末复习 数据结构中有关树的一些知识
金句分享:
✨我将玫瑰藏于身后,风起花落,从此鲜花赠自己,纵马踏花向自由!✨

前言

前面我们介绍的顺序表,链表,队列等都是线性存储结构,即都没有分支,都可以用一条线串起来,那么接下来要讲解的树是有分支的复杂结构.

一、树

1.1 树的概念

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

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

如下图:
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

  • 节点的:一个节点含有的子树的个数称为该节点的
    上图:A的4 B的2

  • 叶节点或终端节点:度为0的节点称为叶节点;
    上图:L、M、N、C、H、I、J、K都是叶节点.

  • 非终端节点或分支节点:度不为0的节点;
    上图:B、D、F、H、I等都是分支结点(非终端结点).

  • 双亲节点父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
    上图:A是B的父节点, B是F的父节点

  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
    如上图:B是A的孩子节点 F是B的孩子节点

  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;
    如上图:B、C是兄弟节点 F和G也是兄弟结点 但是G和H可不是兄弟结点哦,他们不是同一个父亲结点.

  • 树的度:一棵树中,最大的节点的度称为树的度; 如上图:A的度最大,所以树的度为4

  • 节点的层次:用于表示一棵树有多少层.
    从根开始定义起,根为第1层,根的子节点为第2层,以此类推;不要和数组下标从0开始搞混了.

  • 树的高度或深度:树中节点的最大层次;
    如上图:树的高度为4

  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟;
    如上图:G、H互为堂兄弟节点,他们的父亲结点在同一层.

  • 节点的祖先
    从这个结点出发,往上走(父亲结点),直到根节点,这路径的所有结点,都是这个结点的祖先.
    例如:M的祖先是F、B、A

  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

  • 如上图:所有节点都是A的子孙

  • 森林:由m(m>0)棵互不相交的树的集合称为森林.

教大家一个好记的方法,将一棵树的根节点去掉,就是森林了.

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

1.2 树的表示方法:

很明显,树的结构相对于线性表要复杂很多,想要表示并存储树就显得比较麻烦.要保存每个结点的值,还需要表示树的结构,一般有这些表示方法:

1.双亲表示法:

双亲表示法(了解一下思路即可)

采用顺序表存储,将树每个结点除了存储数据以外,还存储其父亲结点的下标.
由于树中每个结点的父亲是唯一的,所以可以采用父亲数组表示法实现唯一地表示任何一棵树。在这种表示法下,寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路,即从一个结点到其父亲结点,再到其父亲的父亲等其他祖先结点,这就可以求出根结点
在树的双亲表示法中,对于涉及查询儿子和兄弟信息的树操作,可能要遍历整个数组。为了节省查询时间,可以规定指示儿子的数组下标值大于父亲的数组下标值,(即儿子下面)而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。(兄弟在边上)

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

根节点由于没有父节点(前驱结点),一般将下标设置为-1.
typedef char DataType;
#define  MAX_Node 20


typedef struct NodeType
{
	DataType  data;		//该结点存储的数据
	int Parent;			//该结点的父亲的数组下标,对于根结点,父亲下标设置为-1
}NodeType;

struct TreeType
{
	int NodeCount;      		//树的结点个数
	NodeType Node[MAX_Node];	//树结点
};

2.孩子表示法:

孩子表示法(不推荐)

方法1:(个人感觉好low)

每个结点有若干个指针域MistyRose,指向其孩子。由于孩子的数目不一,指针域要创建这棵树的度数个,这样每个树结点的结构一样,但是贼浪费空间.特别是有的树结点的度很大,有的很小的时候.

//了解即可
typedef int DataType;
struct Node
{
	DataType _data; // 结点中的数据域
	struct Node* child1;
	struct Node* child2;
	struct Node* child3;
	//........

};

方法2:

由于是存储儿子结点时浪费空间,我们就可以将儿子结点用链表存储。这种表示法用一个线性表来存储树的所有结点信息,称为结点表
对每个结点建立一个孩子表孩子表中只存储孩子结点的地址信息,可以是指针,数组下标。由于每个结点的儿子数目不定,因此儿子表常用单链表来实现。

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

//了解思想即可

//把每个结点的孩子结点排列起来,以单链表作为存储结构
//n个结点有n个孩子链表,如果是叶子结点此单链表为空
//然后n个头指针又组成一个线性表,采用顺序存储结构,放进一个一维数组


typedef struct Node   //孩子结点
{
	int child;    //孩子
	struct Node * next;
}Node;
typedef struct Box  //表头结构
{
	int data;
	Node * FirstChild;
}Box;
typedef struct Tree
{
	Box nodes[MAXSIZE];
	int r, n;     //根的位置    结点数
}Tree;


3. 孩子兄弟表示法

孩子兄弟表示法:(很不错的表示方法)

即树的左边为孩子,右边为兄弟表示法又称为二叉树表示法或二叉链表表示法。
每个结点除了data域(数据域)外,还含有两个域:
①、最左边的孩子 ②、右边的兄弟

可以用一个小故事来方便我们理解.
由于没有计划生育,一对夫妻生的孩子是没有限制的,孩子太多就很难管理,父母为了解决这个问题,先生第一个孩子,等这个孩子长大一点之后,教这个大儿子(最左边的孩子)帮忙带其他孩子(兄弟).父母只需要关注大儿子就好,找到大儿子,就可以找到其他小儿子们了.

图解:
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

示例代码:

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
树形结构在文件系统中得到了应用:

例如:讲解linux基本指令时,提到了linux的文件系统结构图.
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

(图片来源于:百度)

二、"二叉树"的基本概念

2.1 二叉树的介绍

如果说"树"是没有计划生育的,那么"二叉树"就是进行了计划生育的父母,一个父亲结点,至多只能有两个孩子,即每个结点的孩子的个数是:0 1 2
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

各位友友们现实生活中见过二叉树吗?

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

2.2 特殊的二叉树:

  1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值(即有两个孩子),则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为k,且结点总数是2k -1,则它就是满二叉树。

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

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

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

奇怪的二叉树:
只有左孩子的二叉树:

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

只有右孩子的二叉树:

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

2.3 二叉树的性质

  1. 若规定根节点所在层数为1,则一棵非空二叉树的第i层上最多有2k 个结点.

当这颗树是满二叉树时,第k层的结点数为最大值,可以参考上面的满二叉树的图,知道一层最多是2k 个结点.

  1. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2h -1.
  1. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0=n2+1 (这个性质划重点)

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

  1. 若规定根节点的层数为1,具有n个结点的满二叉树的深度log2 (n+1)

三、一些经典的练习题:

1.在一棵具有5层的满二叉树中结点总数为_____.
2.根的层次为1,有64个结点的完全二叉树的深度为____.
3.具有100个结点的完全二叉树的深度为______.
4.已知一棵完全二叉树中共有768个结点,则该树中共有_______个叶子结点。
5.在具有 2n 个结点的完全二叉树中,叶子结点个数为_____.
6.某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为_____.

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

答案:

  1. 31

解释:

5层满二叉树的结点个数是25 -1=31个

  1. 7

解释:

6层满二叉树的结点个数是26 -1=63,则64个结点是七层的,最后一层只有一个叶子结点的完全二叉树.

  1. 7
    解释:

6层最多是26 -1=63个结点,而7层最多是27 -1=127,
64<100<127
故深度比6大,深度是7

  1. 384

解释:

叶子结点即度为0的结点,总共有768个结点.
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念

  1. n
    解释:

和上题一个思路, 2n=(n2+1)+n2+n1,此时不难知道(因为n1=0,则n2就不是整数)n1=1,
故n2=n-1,n0=n

  1. 200(不解释).

今天的期末复习资料就讲到这里了,希望对友友们复习有所帮助.再见啦!

还在担心期末挂科吗? 期末必备复习资料-----“树“的概念文章来源地址https://www.toymoban.com/news/detail-481149.html

到了这里,关于还在担心期末挂科吗? 期末必备复习资料-----“树“的概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《大数据分析入门》期末复习资料

    期末复习资料,仅供参考。 1、数据分析工具不包括以下()选项。 A、SPSSStatisticsB、Matlab2014bC、OFFICEPowerpointD、StyleIntelligence 参考答案:D 2、Excel数据管理中,标记关键数据的方法中能够替代柱形图的是()。 A、色阶区分数据B、条件格式突出C、图标集区分数据D、数据条区分

    2024年02月15日
    浏览(33)
  • 【计算机网络】期末计网复习资料(应该全了)

    计算机网络训练题       自制思维导图 不会有人现在才复习计网吧????????!!!!! 除第一个文件后面都是自己写的答案,不一定准确 目录 计网训练题   计算机网络复习题---选择题专项训练 计网问答计算练习 第一部分 基本知识 l  TCP/IP的传输层议不能提供无

    2024年02月03日
    浏览(46)
  • Python期末复习知识点大合集(期末不挂科版)

    本期博客总结了老师给出的考试范围的相关知识点,知识点总结的并不是很完整,更多详细细致的知识点可以去看一下我的Python专栏: Python编程基础 Python每日一学 知识点总结仅供参考,总结不易,期待得到你们的点赞收藏转发三连,谢谢!祝大家期末考试顺利通过!!!

    2024年02月03日
    浏览(51)
  • 【一起啃西瓜书】机器学习-期末复习(不挂科)

    马上西瓜书期末考试,为了不挂科,需要有针对复习,内容来自专业各个学霸及老师的重点划分。 推荐: 【一起啃西瓜书】机器学习总览 卷面共100分,含5种题型,考试时间120分钟。 判断题,8道,每题2分,共16分; 填空题,7道,每题2分,共14分; 简答题,5道,每题4分,共20分; 演

    2024年02月08日
    浏览(49)
  • 大数据技术期末复习重点,不挂科看这里~

    本篇文章是根据老师画的重点,作为期末大数据复习资料,持续更新中~ 目录 一、大数据概念 1.什么是大数据,大数据的意义是什么?大数据的特征是什么? 2.大数据的技术支撑是什么? 3.大数据的处理方法有哪些? 二、数据采集与预处理 1.Kafka数据采集 2.数据预处理原理

    2024年02月11日
    浏览(43)
  • 计算机网络期末复习速通--不挂科版

    特别注意: 数据块的单位和网络速率的单位 eg:数据块单位 K = 2的10次方 网络速率单位 K=10的三次方 第一章 概述 重点 : 分组交换-存储转发 计算机网络的类别和计算机网络的性能名词解释 发送时延、传播时延 计算机网络分层次的体系结构,包含协议和服务的概念 1.1计算机网

    2024年02月11日
    浏览(53)
  • 【网络协议详解】——知识点复习(期末不挂科版)

    课本: 网络协议分析的方法: 静态的代码分析、动态的流量分析 IOS 的命令行接口(Command-Line Interface,CLI)是配置、监控和维护 Cisco 设备的最主要用户接口。 CLI 有多种模式: 命令模式 访问方法 提示符 退出方法 用途 User EXEC(用户模式) 连接设备 Router 输入命令 logout 或

    2024年02月09日
    浏览(54)
  • 【计算机网络详解】——知识点复习(期末不挂科版)

    配套视频:湖科大教书匠 配套教材:计算机网络(第8版) 谢希仁 根据学习通要求“掌握”的部分总结的, 有亿点点长 ,时间来不及就掌握画 ☆ 的就好啦 交换方式 特点 优点 缺点 电路交换 预先建立通信路径 传输稳定,延迟低 资源浪费,不适用于并发 报文交换 直接传输

    2024年02月10日
    浏览(41)
  • 【Python数据结构与算法】—— 搜索算法 | 期末复习不挂科系列

    ​ 🌈个人主页:  Aileen_0v0 🔥系列专栏:  数据结构与算法 💫个人格言: \\\"没有罗马,那就自己创造罗马~\\\" 这篇博客主要探索的是计算机科学常见问题---搜索算法 “时间紧,任务重!” 话不多说,开始今天的学习之旅吧⛵~ 目录 搜索 定义 -in 顺序搜索  无序表的顺序搜索

    2024年02月05日
    浏览(49)
  • 云计算复习资料

    云计算是以硬件服务器为基础,通过将硬件资源整合、池化,作为资源的服务端,从而向用户端提供基础资源 服务 。 (1)自助式服务 (2)随时随地使用 (3)可度量的服务 (4)快速资源扩缩 (5)资源池化 云计算是分布式计算、并行计算、效用计算、虚拟化、网络存储、负载

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包