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

初阶牛

发布于 2023-10-14 17:38:35

3370

文章被收录于专栏：C语言基础C语言基础

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯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 特殊的二叉树:

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

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

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

只有右孩子的二叉树:

2.3 二叉树的性质

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

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

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2h -1.

对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0＝n2＋1 (这个性质划重点)

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

三、一些经典的练习题:

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

答案:

解释: