🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯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 的结点,则该二叉树中的叶子结点数为_____.
答案:
- 31
解释:
5层满二叉树的结点个数是25 -1=31个
- 7
解释:
6层满二叉树的结点个数是26 -1=63,则64个结点是七层的,最后一层只有一个叶子结点的完全二叉树.
- 7
解释:
6层最多是26 -1=63个结点,而7层最多是27 -1=127,
64<100<127
故深度比6大,深度是7
- 384
解释:
叶子结点即度为0的结点,总共有768个结点.
- n
解释:
和上题一个思路, 2n=(n2+1)+n2+n1,此时不难知道(因为n1=0,则n2就不是整数)n1=1,
故n2=n-1,n0=n
- 200(不解释).
今天的期末复习资料就讲到这里了,希望对友友们复习有所帮助.再见啦!文章来源:https://www.toymoban.com/news/detail-481149.html
文章来源地址https://www.toymoban.com/news/detail-481149.html
到了这里,关于还在担心期末挂科吗? 期末必备复习资料-----“树“的概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!