【数据结构】树和森林

树的存储结构

1. 双亲表示法

定义结构数组，存放树的结点，每个结点含两个域：

​ 数据域：存放结点信息

​ 双亲域：指示结点的双亲结点在数组中的位置

typedef struct PTNode{
    TElemType data;
    int parent;
}PTNode;

#define MAX_TREE_SIZE 100
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;		//根节点的位置和结点个数
};

2. 孩子链表

把每个结点的孩子结点排列起来，看成一个线性表，用单链表存储

则n个结点有n个孩子链表（叶子的孩子链表为空表）。

n个头指针又组成一个线性表，用顺序表存储

孩子结点结构：

| child | next |

typedef struct CTNode{
    int child;
    struct CTNode *next;
}*ChildPtr;

双亲结点结构：

| data | firstchild |

typedef struct{
    TElemType data;
    ChildPtr firstchild;//孩子链表头指针
}CTBox;

树结构：

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;	//结点数和根节点位置
}CTree;

3. 孩子兄弟表示法

实现：用二叉链表作为树的存储结构，链表中的每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

树和二叉树的转换

树转换成二叉树

1. 加线：在兄弟之间加一条线
2. 抹线：对每个结点，除了其左孩子外，去除其余孩子之间的关系
3. 旋转：以根节点为轴心，整体顺时针转45°

二叉树转换成树

1. 加线：若p结点时双亲结点的左孩子，则将p的右孩子，右孩子的右孩子…沿分支找到的所有右孩子，都与p的双亲用线连起来
2. 抹线：抹掉原二叉树中双亲与右孩子的连线
3. 调整：将结点按层次排列，形成树的形状

森林和二叉树的转换

森林转换成二叉树

1. 将各棵树分别转换成二叉树
2. 将每棵树的根节点用线相连
3. 以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树

二叉树转换成森林

1. 抹线：将二叉树中根节点与其右孩子连线，即沿右分支搜索到的所有右孩子之间的连线全部抹掉，是之变成孤立的二叉树
2. 还原：将孤立的二叉树还原成树

树和森林的遍历

树的遍历

1. 先根遍历：若树不空，先访问根节点，然后依次先根遍历各子树
2. 后根遍历：若树不空，先依次后根遍历各子树，然后访问根节点
3. 层次遍历：若树不空，则自上而下、自左而右访问树中的节点

森林的遍历

将森林看作三部分

1. 森林中第一棵树的根节点
2. 森林中第一棵树的子树森林
3. 森林中其它树构成的森林

先序遍历：

若森林不空，则

1. 访问森林中第一棵树的根节点
2. 先序遍历森林中第一棵树的子树森林
3. 先序遍历森林中其它树构成的森林

即：依次从左到右对森林中的每一棵树进行先根遍历

中序遍历：

若森林不空，则

1. 中序遍历森林中第一棵树的子树森林
2. 访问森林中第一棵树的根节点
3. 中序遍历森林中其它树构成的森林

即：依次从左到右对森林中的每一棵树进行后根遍历