一、树的存储
1. 双亲表示法
双亲表示法使用一个顺序表来存储树中的节点，同时为表示节点间的关系，在每个节点中附设一个指示器来表示其双亲节点在此表中的位置，其节点结构如下
| Data | Parent |
|---|
双亲表示法的存储结构定义为：
#define MAX 100
typedef struct TNode
{
DataType data;
int parent;
}TNode;
typedef struct /*树的定义*/
{
TNode tree[MAX];
int root; /*根节点在表中的位置*/
int num; /*该树的节点个数*/
}PTree;
双亲表示法利用的是树中每个节点（除根节点外）只有一个双亲的性质，使得其存储结构很简单，用双亲表示法查找某个节点的双亲非常容易。反复使用求双亲的操作，也可比较容易的找到树的根节点。但是在这种存储结构中，求某个节点的孩子时需要在整个数组中搜寻，以找出其双亲为该节点的节点。
2. 孩子表示法
孩子表示法是把每个节点的孩子存到一个单链表中，称为孩子链表，n个节点共有n个孩子链表（叶子节点的孩子链表为空链表）。n个节点的数据和n个孩子链表的头指针又用一个顺序表存储。
孩子表示法的存储结构定义如下：
typedef struct ChildNode /*孩子链表节点结构定义*/
{
int Child;
struct ChildNode* next;
}ChildNode;
typedef struct /*顺序表节点结构定义*/
{
DataType data;
ChildNode *FirstChild;
}DataNode;
typedef struct /*树的定义*/
{
DataNode nodes[MAX];
int root; /*该树的根节点在顺序表中的位置*/
int num; /*该树的节点个数*/
}CTree;
孩子表示法可以方便的找到结点的孩子，但却不方便寻找结点的双亲，为此可以将孩子表示法与双亲表示法结合起来，即在每个节点结构中增设一个Parent域，形成带双亲的孩子表示法。
3. 孩子兄弟表示法
孩子兄弟表示法又称为树的二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个节点有两个指针域，分别指向第一个孩子和节点的右兄弟
孩子兄弟表示法存储结构定义如下：
typedef struct CSNode
{
DataType data;
struct CSNode* FirstChild;
struct CSNode* NextSibling;
} CSTree;
孩子兄弟表示法便于实现树的各种操作，例如，要访问节点x的第i个孩子，可以先从FirstChild域找到第一个孩子节点，然后沿着NextSibling连走i-1步便可找到x的第i个孩子。如果在孩子兄弟表示法中为每个节点增设一个parent域，则同样可以方便的地实现查找双亲的操作。
孩子兄弟表示法的本质是二叉链表结构，这种存储结构能够帮助实现树和二叉树的相互转换。
二、树和森林的转换
1. 树转换为二叉树
（1）加线：树中所有相邻兄弟之间加一条连线
（2）删线：对每个节点只保留与其第一个孩子节点之间的连线，删掉该节点与其他孩子节点之间的连线
（3）旋转调整：以树的根节点为轴心，将整颗树顺时针旋转一定的角度，使之层次结构清晰、左右子树分明。
2. 森林转换为二叉树
（1）转换：将树中的每一棵树均转换成相应的二叉树
（2）加线：将相邻的各棵二叉树的根节点之间加线，使之连为一体
（3）旋转调整：以第一棵二叉树的根节点为轴心，将整棵树顺时针旋转一定的角度，使之层结构清晰、左右子树分明。即依次把后一棵二叉树的根节点调整到作为前一棵二叉树根节点的右孩子位置
3. 二叉树转换为森林
（1）加线：若某节点是其双亲的左孩子，则把该节点的右孩子、右孩子的右孩子、……都与该节点的双亲节点加上线
（2）删线：删掉原二叉树中所有双亲节点与右孩子间的连线
（3）旋转调整：旋转整理由（1）、（2）两步所得到的各棵树，使之结构清晰、层次分明。
4. 森林转换为二叉树的递归定义 P146
5. 二叉树转换成森林的递归定义 P146
三、树和森林的遍历
1. 树的遍历
（1）先根遍历
若树非空，则按如下规则遍历
① 访问根节点
② 从左到右，依次先根遍历根节点的每一棵子树
（2）后根遍历
若树非空，则按如下规则遍历
① 从左到右，依次后根遍历根节点的每一棵子树
② 访问根节点
仔细观察可发现，树的遍历序列与树转换的二叉树的遍历序列有如下对应关系
（1）树的先根遍历序列对应于转换的二叉树的先序遍历序列
（2）树的后根遍历序列对应于转换的二叉树的中序遍历序列
2. 树的遍历算法（P147）
3. 森林的遍历
（1）先序遍历
若森林非空，则按如下规则遍历
① 访问森林中第一棵树的根节点
② 先序遍历第一棵树中根节点的子树森林
③ 先序遍历除去第一棵树之后剩余的树构成的森林
（2）中序遍历
若森林非空，则按如下规则遍历
① 中序遍历森林中第一棵树的根节点的子树森林
② 访问第一棵树的根节点
③ 中序遍历除去第一棵树之后剩余的树构成的森林
森林的先序遍历、中序遍历与对应二叉树的先序遍历、中序遍历序列是对应的；
把一棵树看成是森林，则森林的先序遍历和中序遍历分别与树的先根遍历和后根遍历相对应。
网友评论