学习笔记——树

AI摘要
加载中...
摘要由AI自动生成,仅供参考!

tree

介绍

  • n(n>0)个元素组成的有限结合,是一种非线性的有序结构。
  • 每一个其中的元素都被称为结点,除根节点外,其余节点组成的子集称为子树。
  • 一棵树由根节点与结点组成,除根节点外每个节点都有前驱结点。一棵树至少有一个节点,此时,该节点即为根节点。换而言之,每棵树有且仅有一个根节点。在一个mk叉数中最多有1km+11k\frac{1-k^{m+1}}{1-k}个节点(k>=1, m>=0)。
  • 树是递归定义的,即在一棵子树中,其根节点同样在树中作为结点。
  • 一个节点的子树个数称为这个节点的度(degree)。度为零的节点称为叶节点(leaf),不为零的节点称为分支节点(包括根节点),根以外的分支节点被称为内部节点。一棵树中度最大的节点的度被称为这棵树的度。
  • 树状结构的图形中,连接两个相关联的结点的线段称位树枝。上端节点为下端节点的父节点,相对应的下端节点为上端节点的子节点,同一个父节点的所有子节点互为兄弟结点。从根节点出发到某个子节点所经过的所有节点均为该子节点的祖先,同理,此此节点为其所有祖先的子孙。
  • 一棵树中根节点的层次(level)0,其余的节点的层次为其父节点的层次加1。与度一样,树中层次最大的节点的层级被称为树的深度(depth)。
  • 在树中,从一个节点出发,自上而下的沿着节点与树枝可以到达另一节点,则称它们间存在一条路径(所以显而易见不同子树上的节点间不存在路径)。用路径上的节点个数减一(即树枝个数,或是用层级较大的节点的层数减去较小的节点的层数)表示路径长度。
  • 互不相交的数的集合称为森林,即森林是m棵互不相交的树的集合。

如下图即为一颗经典的树:

存储结构

父亲表示法
1
2
3
4
#define MAX_LENGTH 10 //最大节点数
struct node { //定义节点
int data, father; //作用域与指针域
}tree[MAX_LENGTH]; //定义树

这种方法容易找到树根,但是找孩子就需要遍历整个线性表,即时间换空间

孩子表示法
1
2
3
4
5
6
7
8
#define MAX_DEGREE 10 //最大度数
struct node {
int data; //数据域
node* children[MAX_DEGREE]; //指向若干个子节点的指针域
};
struct tree {
node* root;
}t;

这种方法不可以从子节点返回父节点

父亲孩子表示法
1
2
3
4
5
6
7
8
#define MAX_DEGREE 10 //最大度数
struct node {
int data; //数据域
node* children[MAX_DEGREE], father; //指向若干个子节点的指针域
};
struct tree {
node* root;
}t;

是孩子表示法的优化版,可以直接访问任意子节点的父节点,是一种空间换时间的方法

孩子兄弟表示法
1
2
3
4
5
6
7
struct node {
int data; //数据域
node* firstChild, next; //分别指向第一个子节点与下一个兄弟节点
};
struct tree {
node* root;
}t;
总结

这些方法没有好坏之分,应当视情况选用

遍历

  • 先序遍历(深度优先搜索dfs,从左至右先输出再搜索)
  • 后序遍历(深度优先搜索dfs,从左至右先搜索到叶节点再依次输出并回溯)
  • 层次遍历(广度优先搜索bfs,按层次从左至右搜索,搜索完一层后搜索下一层)
  • 叶节点遍历(按先序遍历的方法遍历,但只访问叶节点)

题外话

这玩意是放暑假前在学校无聊看《信息学奥赛一本通》写的,大概还是有参考价值的吧。

另外还有一篇二叉树的,大概也会发上来。


学习笔记——树
https://www.ordchaos.com/posts/d4140423/
作者
序炁
发布于
202271
更新于
202271
许可协议