2023年学习记录 - 树和森林

声明

本节内容来源于 BiliBili视频数据结构与算法基础（青岛大学-王卓） 的 P95 - P100，本博客仅作笔记整理和学习记录，部分图片来自视频截图。

树和森林

定义：传送门

树的存储结构

双亲表示法（静态链表）

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

• 数据域：存放结点本身信息。
• 双亲域：指示本结点的双亲结点在数组中的位置。

特点：找双亲容易，找孩子难。

typedef struct PTNode{
  TElemType data;
  int parent;     //双亲位置域
}PTNode;

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

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储。则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

特点：找孩子容易，找双亲难。

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

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

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

可以使用带双亲的孩子链表：以空间换时间

孩子兄弟表示法（二叉树表示法，二叉链表表示法）

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

typedef struct CSNode{
  ElemType data;
  stryct 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. 中序遍历森林中（除第一棵树之外）其余树构成的森林。

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