数据结构（六）：树

一、树的定义

ADT Tree{
​ 数据对象：
​ D={1=<i<=n, n>=0, a(i)属于 ElemType类型}
​ 数据关系：
​ R={<a(i), a(j)> | a(i), a(j)属于 D, 1=<i<=n, 1=<j<=n, 其中每个元素只有一个前驱，可以有零个或多个后继，有且仅有一个元素没有前驱}
​ 基本运算：
​ InitTree(&t)：初始化树：构造一棵空树 t。
​ ClearTree(&t)：销毁树：释放树 t所占胡空间。
​ Parent(t)：求元素 t的前驱。
​ Sons(t)：求元素 t的所有后继。
}

二、树的存储结构

1、双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有节点，

同时在每个节点中设置一个伪指针指示双亲节点的位置。
结构体类型定义：

typedef struct{
    ElemType data;
    int parent;
} PTree[MaxSize];

2、孩子存储结构

这种存储结构中，每个节点不仅包含数据，还包括指向所有孩子节点的指针。
按照树的度设计节点的最大孩子节点个数。
结构体定义如下：

typedef struct node{
    ElemType data;
    struct node* sons[MAX_SONS];
} TSonNode;

3、孩子兄弟链存储结构

这个存储结构为每个节点设计三个域：一个数据元素域、一个指向当前节点第一个字节点的指针域、一个指向该节点下一个兄弟节点的指针域。
结构体类型定义：

typedef struct tnode{
    ElemType data;
    struct tnode* first_son;
    struct tnode* next_brother;
} TSBNode;

三、树的基本运算

1. 寻找某种满足特定关系的节点，如寻找当前节点的双亲节点。
2. 插入或删除某个节点，如在树的当前节点上插入一个新节点或删除当前节点的第 i个孩子节点。
3. 遍历树中的每个节点。

1、树的遍历

1、先根遍历

​ （1）访问根节点。

​ （2）按照从左到右的顺序先根遍历根节点的每一棵子树。

2、后根遍历

​ （1）按照从左到右的顺序后根遍历每一棵子树。

​ （2）访问根节点。