树 树结构
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了树 树结构,现在分享给大家,供学习和参考。文章包含2331字,纯文字阅读大概需要6分钟。
教程信息
一、树的概念
(一)树
1、树:
树是一种非线性的、一对多的数据结构,由n(n>0)个元素组成的有限集合,其中:
(1)每个元素称为
结点(node)
,有一个特定的结点,称为根结点
或树根(root)
(2)除根结点外,其余结点能分成若干互不相交的有限集合,每个子集又都是一棵树(称为树的子树)
(3)树是递归定义的,根结点没有前驱,其余每个结点都有唯一前驱,每个结点可以有0或多个后继结点
图中是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。
对于数据 A 来说,和数据 B、C、D 有关系;
对于数据 B 来说,和 E、F 有关系。这就是“一对多
”的关系。
整个存储形状在逻辑结构上看,类似于实际生活中倒着的树,所以称这种存储结构为“树型”存储结构。
2、子树
整棵树的根结点为结点 A,
而如果单看结点 B、E、F、K、L 组成的部分来说,也是棵树,而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树;
同样,结点 E、K、L 构成的也是一棵子树,根结点为 E。
特别有,单个结点也是一棵树,只不过根结点就是它本身。如,结点 K、L、F 等都是树,且都是整棵树的子树。
知道了子树的概念后,树也可以这样定义:树是由根结点和若干棵子树构成的。
3、森林
由 m(m >= 0)个互不相交的树组成的集合被称为森林。
树可以理解为由根结点和若干子树构成,若干子树本身是一个森林,所以树还可以理解由根结点和森林组成,如上面的树就是由下列三棵树和根节点A构成。
(二)树的结点
使用树结构存储的每一个数据元素都被称为“结点”
。不同结点之间可能存在关系,主要的关系包括:
1、父子关系
(1)孩子结点/子结点:
一个结点下面的直接连接的结点。如BCD都是A的
子结点
(2)双亲结点/父结点:
一个结点的上一级结点。如B是EF的父结点,C是G的
父结点
(3)兄弟结点:
同一个双亲结点的子结点,互为
兄弟结点
。如BCD互为兄弟结点,EF互为兄弟结点(4)叶子结点/叶结点:
如果结点没有任何子结点,那么此结点称为
叶子结点
。如KLFGMIJ 都是叶子结点(5)分支结点:
如果一个结点有子结点,那么此结点成为
分支结点
,根以外的分支结点又称为内部结点
。如BCD(6)根节点:
如果结点没有父节点,那么此节点称为
根节点
,一棵树只有一个根节点。如A
2、祖孙关系
(1)祖先结点:
一个结点的全部上级结点,包括父结点、父结点的父结点……直到根结点。
如E的祖先结点有AB
(2)孙子结点:
一个结点的全部下级结点,包括子结点、子结点的子结点……直到叶子结点。
如B的孙子结点有EFKL
(三)树的属性
1、度
结点拥有的子树数(结点有多少分支)称为结点的度,各结点度的最大值称为树的度。
(1)叶子结点/树叶:
度为0的结点(结点KLFGMIJ)
(2)分支节点:
度不为0的结点(结点ABCDEH)
2、深度/高度
(1)结点的层次:定义一棵树的根结点的层次为1,其它结点的层次等于它的父结点层次加1
结点BCD的层次为2,结点EFGHIJ的层次为3,结点KLM的层次为4
(2)一棵树中所有的结点的层次的最大值称为树的深度/高度
这棵树的深度为4。
二、树的性质
1、根节点没有父节点,其他点只有一个父节点
2、n个结点的树,有且仅有n-1条边(将树看成一个无边结点(根节点)和n-1个带一条边结点拼成的积木)
3、树中任意两个结点之间,有且仅有一条路径,并且树结构中不存在环路
三、树的存储方法
树的存储在STL中没有直接实现,通常使用数组或者链表+结构体的方法进行模拟
(一)链式存储方式
每个节点都由一个数据域和若干个指针域组成,通过链表构造树
1、孩子表示法:
每个节点有两个域——数据域data和孩子域child
(1)使用数组模拟:
这种方法显然是很浪费空间的,因为有很多结点,它的指针域都是空的
(2)改良方法:
直接使用STL的vector存储孩子
2、双亲表示法:
每个节点都有两个域——数据域data和双亲域parent和孩子表示法类似,只不过当算法中需要在树结构中频繁地查找某结点的父结点时,使用双亲表示法最合适。当频繁地访问结点的孩子结点时,双亲表示法就很麻烦,孩子表示法更适合。
3、双亲孩子表示法:
每个节点有三个域——数据域data,孩子域child和双亲域parent。
是孩子表示法与双亲表示法的综合,可以顺利访问每个结点的父节点和孩子结点,缺点是增加了存储空间。
4、孩子兄弟表示法:
每个节点有三个域——数据域data,第1个孩子域lchild,右兄弟域rchild
任意一个树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此设置两个指针,分别指向该结点的第一个孩子和此节点的右兄弟。
通过孩子兄弟表示法,普通树转化为了二叉树,所以孩子兄弟表示法又被称为“二叉树表示法”或者“二叉链表表示法”。同时这种表示法,给查找某个结点的某个孩子带来了方便。
一般而言,该方法一般只适用于非二叉的普通树。
(二)数组存储方式
按照某种遍历方式依次将每个节点存储在数组中,通过适当的遍历方法访问数据。
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供树 树结构的全部内容,希望教程文章能够帮你了解学习树 树结构,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-294.html