淘宝建设网站的理由,杭州建设厅官方网站,wordpress主题图标乱码,seo每天一贴博客文章目录一、1.树是什么#xff1f;2.树的特点二、树的相关概念三、树的表示方法1.常规方法表示树2.使用左孩子右兄弟表示法3. 使用顺序表来存储父亲节点的下标三、树在实际的应用总结一、1.树是什么#xff1f;
树是一种非线性的数据结构#xff0c;它是由n#xff08;n2.树的特点二、树的相关概念三、树的表示方法1.常规方法表示树2.使用左孩子右兄弟表示法3. 使用顺序表来存储父亲节点的下标三、树在实际的应用总结一、1.树是什么
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
2.树的特点
1.有一个特殊的结点称为根结点根节点没有前驱结点 2.除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 3.因此树是递归定义的。
二、树的相关概念
以这张图为例 加粗的概念特点是需要记住的没有加粗的概念了解就行。
1.节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6
2、叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点
3、非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点
4、双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点
5、孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点
6、兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点
7、树的度一棵树中最大的节点的度称为树的度 如上图树的度为6
8、节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推
9、树的高度或深度树中节点的最大层次 如上图树的高度为4 需要注意的是树的高度有两种说法 第一种说法是以0为开始计算树的高度仿照数组下标从0开始 但是这样计算的缺点是假如一棵树是空树就得从-1开始不太符合常理。 第二种说法就是从1开始这种是推荐的。 10、堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点
11、节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先
12、子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙
13、森林由mm0棵互不相交的树的集合称为森林
三、树的表示方法
1.常规方法表示树
所谓常规方法就是定义一个结构体每个节点的度是多少就定义多少个指针变量来存放子节点的地址。
但是这样做非常挫 因为不是每个节点的度都相同有可能有的节点的度是8个有的节点的度是1个 那么剩下的七个指针变量就没有用处了。 所以这种方法不可取。
2.使用左孩子右兄弟表示法 左孩子右兄弟表示方法如上图 每个节点都只使用两个指针变量一个指针变量存放该节点的第一个孩子的地址另一个指针变量存放该节点的兄弟节点。
同层级是兄弟关系上下层级是亲子关系。
这样做的优点是不管一棵树有多少个节点一定能够使用这种方法表示整个树的结构。
结构体源码如下
typedef int BTDataType;
struct Node
{
struct Node* firstChild; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
BTDataType data; // 结点中的数据域
};
3. 使用顺序表来存储父亲节点的下标 以上图为例 A是整棵树的根节点所以A没有父节点它的下标存储-1代表没有父节点B~G的父亲节点都是A所以 B ~ G 存储的下标都是A的下标也就是0代表它们的父亲节点在下标为0位置处。 其他的以此类推。
三、树在实际的应用 这是一棵典型的树可以用来表示文件目录。
总结
树是一种特殊的数据结构在实际生活种有很多用处学好树就是一个质的飞跃
