数据结构之树的概念以及结构

举报
为世界献上祝福 发表于 2022/10/29 20:58:11 2022/10/29
【摘要】 数据结构之树的概念以及结构1.树的概念树是一种非线性的数据结构,是由n(n>=0)有限节点的组成的一个具有线性关系的集合。叫树的原因是因为它看起来像是一颗倒挂的树,只不过是根朝上,叶朝下1. 树的一个特殊节点叫做根节点 ,根节点没有前驱节2. 除了根节点之外,其余节点被分割M个互不相交的集合T1,T2......,而每个集合都是与树结构相同的子树,每个子树都有属于它自己的‘根节点’,可以有0...

数据结构之树的概念以及结构

1.树的概念

树是一种非线性的数据结构,是由n(n>=0)有限节点的组成的一个具有线性关系的集合。

叫树的原因是因为它看起来像是一颗倒挂的树,只不过是根朝上,叶朝下

1. 树的一个特殊节点叫做根节点 ,根节点没有前驱节

2. 除了根节点之外,其余节点被分割M个互不相交的集合T1,T2......,而每个集合都是与树结构相同的子树,每个子树都有属于它自己的‘根节点’,可以有0个或多个后继

3. 由此可以看出来树的定义是递归的!


子树与子树之间是不能有交集的,否则就不是树的结构!



2.树的相关概念

在·

1. 节点的度:一个节点所含有的子树的个数称为该节点的!例如A的度就是6,因为A有6个子树

度的概念是相对于节点而言的,每个节点都有属于它的度!子树要整体的去看(或者直接看该节点的分支有几个)例如E包括它以下的所有节点都是属于A的一颗子树!但是I,还有J以下的所有节点是属于E的两颗子树!

2. 叶节点或终端节点:度为0的节点就是叶节点(终端节点),例如H,I,P,Q,K,L.......

3. 非终端节点或者分支节点:度不为0的节点 ,与叶节点(终端节点)相对的概念。例如:E,J,F,G.....

4. 父节点或双亲节点:含有子节点的节点就是其子节点的父节点(双亲节点)。

父节点与子节点身份同时存在不冲突!例如E是,I,J这两个节点的父节点,又是A的子节点!

5. 子节点或孩子节点:一个节点含有的子树的节点称之为该节点的子节点

说实话这句话说的挺绕的,其实就是这个节点上面连着一个节点,这就是上面那个节点的子节点

6. 兄弟节点:有同一个父节点的节点彼此之间就是兄弟节点

有同一个爸就是兄弟!

7. 树的度:一棵树中,最大节点的度称之为该树的度。例如上面的树的度就是6.

每个节点都有属于它自己的度!而其中最大的那个度就是该树的度!(那个度不一定存在于根节点!)

8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推

根节点开始数起!是下面概念的基础

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

10. 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点

11. 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

再例如E是 I,J,P,Q的祖先,但是不是K,L的祖先,因为E的分支没有经过K.L。

12. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

子,父,祖先,子孙这几个概念互不冲突,可以同时存在于一个节点,只是可能对象不一样!

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

应用并查集

3.树的结构

关于树的结构的定义有

struct TreeNode
{
int date;
struct TreeNode* child1;
struct TreeNode* child2;
struct TreeNode* child3;
struct TreeNode* child4;
// ........
}


这种结构的坏处在定义繁琐!在不知道度的情况下很麻烦!

除非给了固定的度的大小!

#define N 5
struct TreeNode
{
int date;
struct TreeNode* children[N];
int childsize;
}//这种结构是类似于静态的顺序表!但是这样很浪费!

在上面的基础上进一步改进

struct TreeNode
{
int date;
//用一个顺序表存储孩子节点的指针!
struct TreeNode** children;//为什么要二级指针呢?因为要存储数据是数组的指针,所以要二级指针数组来存储!
int childsize;
int childcapacity;
}

但是的上面的所有结构都不是最优解!

虽然更加的直观!但是还是不够方便!

所以引入了一种新结构!左孩子右兄弟!

typedef int DateType;
struct TreeNode
{
struct TreeNode* Child;// 第一个孩子结点
struct TreeNode* brother;// 指向其下一个兄弟结点
DateType date;//存储数据!
}


如图:A指向它的第一个孩子B,因为A没有兄弟则兄弟指向空!

然后再B指向它的第一个孩子,然后指向它的兄弟C

......

这样子就可以通过兄弟找兄弟!

该结构的运用!

void printTree(struct TreeNode* parent)
{
if(parent == NULL)
return;
struct TreeNode* cur = parent;
while(cur)
{
printf("%d",cur->date);//先访问当前节点
printTree(cur->child);//访问自孩子节点
cur = cur->brother//再访问兄弟节点!
}
}

初次之外还有一个双亲表示法


这种方式方便找祖先!

4.树在实际中的运用(表示文件系统的目录树结构)


【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。