学习笔记——树

树tree

介绍

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

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

存储结构

父亲表示法

#define MAX_LENGTH 10 //最大节点数
struct node { //定义节点
    int data, father; //作用域与指针域
}tree[MAX_LENGTH]; //定义树

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

孩子表示法

#define MAX_DEGREE 10 //最大度数
struct node {
    int data; //数据域
    node* children[MAX_DEGREE]; //指向若干个子节点的指针域
};
struct tree {
    node* root;
}t;

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

父亲孩子表示法

#define MAX_DEGREE 10 //最大度数
struct node {
    int data; //数据域
    node* children[MAX_DEGREE], father; //指向若干个子节点的指针域
};
struct tree {
    node* root;
}t;

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

孩子兄弟表示法

struct node {
    int data; //数据域
    node* firstChild, next; //分别指向第一个子节点与下一个兄弟节点
};
struct tree {
    node* root;
}t;

总结

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

遍历

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

题外话

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

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