408数据结构-树与森林 自学知识点整理

前置知识：树的基本概念与性质

树的存储结构

树既可以采用顺序存储结构，又可采用链式存储结构。但无论采取哪种方式，都要求能够唯一地反映树中各结点之间的逻辑关系。

1. 双亲表示法

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点增设一个伪指针，指示其双亲结点在数组中的位置。

#define MAX_TREE_SIZE 100
typedef struct ElemType {
	int value;
}ElemType;//预处理

typedef struct {
	ElemType data;
	int parent;//双亲位置域
}PTNode;
typedef struct {//树的类型定义
	PTNode nodes[MAX_TREE_SIZE];//双亲表示
	int n;//结点数
}PTree;

双亲表示法利用了除根结点以外每个结点只有唯一双亲的性质，优点是可以很快地得到每个结点的双亲结点，但缺点也很明显，求结点的孩子时需要遍历整个结构。
使用双亲表示法存储树时，删除结点共有两个方法：

• 一是直接把需要删除的结点$parent$值置$-1$，表示当前结点为空（根结点默认存放在$nodes[0]的位置$，且$parent$值也为$-1$，需要特别判断）。但是这种方法在遍历找孩子时，会使得遍历过程要经过一个或多个空结点，徒增时间复杂度。
• 二是把需要删除的结点和数组末尾元素交换，然后结点数n--。这种方法要优于方法一。

2. 孩子表示法

孩子表示法是将每个结点的孩子视为一个线性表，且以单链表作为数据结构，这样$n$个结点就有$n$个孩子链表（叶结点的孩子链表视为空表）。

struct CTNode {//单链表（B站弹幕说是邻接表）
	int child;//孩子节点在数组中的位置
	struct CTNode* next;//下一个孩子
};
typedef struct {
	ElemType data;
	struct CTNode* firstChild;//第一个孩子
}CTBox;
typedef struct {
	CTBox nodes[MAX_TREE_SIZE];//孩子表示法
	int n, r;//结点数和根的位置
}CTree;

与双亲表示法相反，孩子表示法寻找结点孩子的操作非常方便，但是寻找双亲的操作则需要遍历$n$个结点中孩子链表指针域所指向的$n$个孩子链表。同样的，可以顺着这个思路思考，如何实现孩子表示法存储的树的增删查改等基本操作。

3.孩子兄弟表示法⭐

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针。

typedef struct CSNode {//孩子兄弟表示法
	ElemType data;//数据域
	struct CSNode* firstchild, * nextsibling;//第一个孩子和右兄弟指针
}CSNode, * CSTree;

使用这种方法最大的优点就是可以实现将树转换为二叉树的操作，优缺点与二叉树的链式存储结构相同，这里不再展开。

树、森林与二叉树的相互转换

从物理结构上看，树的孩子兄弟表示法和二叉树的二叉链表表示法是相同的。因此可以用同一存储结构的不同解释将一棵树转换为二叉树。

$1)$树转换为二叉树

树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则也称“左孩子右兄弟”。由于根结点没有兄弟，因此树转换得到的二叉树没有右子树，如图所示。 （图片来自王道考研408数据结构2025）

树转换为二叉树的画法：
①在兄弟结点之间加一条线；
②对每个结点，只保留它与第一个孩子的连线，与其他孩子的全部抹掉；
③以树根为轴心，顺时针旋转45°。
二叉树转换为树逆着来就行。

$2)$森林转换为二叉树

森林转换为二叉树的规则与树类似，只需要把每一棵树的根结点都看成兄弟，依次连在第一棵树根结点的右子树上即可。
森林转换为二叉树的画法：
①将森林中的每棵树转换成相应的二叉树；
②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
③以第一棵树的根为轴心，顺时针旋转45°。
二叉树转换为森林同样逆着来就行，这里就不再展开。

树和森林的遍历

前置知识：二叉树的遍历

1. 树的遍历

树的遍历是指用某种方式访问树中的每个结点。主要有两种方法：

$1)$先根遍历。若树非空，则按如下规则遍历：

• 先访问根结点。
• 再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。

void Visit(CSNode* T) {
	cout << T->data.value << " ";
	return;
}

void PreOrder(CSTree T) {//先根遍历（使用孩子兄弟表示法）
	if (T != NULL) {
		Visit(T);//访问根结点
		CSTree C = T->firstchild;//C记录当前树根结点的第一个孩子
		do {//首先对以C为根的子树进行先根遍历
			PreOrder(C);
			C = C->nextsibling;//再依次对C的右兄弟为根的子树进行先根遍历
		} while (C != NULL);//当C还有其他右兄弟时循环继续
	}
	return;
}

其遍历序列与这棵树对应的二叉树的先序序列相同。

$2)$后根遍历。若树非空，则按如下规则遍历：

• 先依次遍历根结点的每棵子树，遍历子树是仍遵循先子树后根的规则。
• 再访问根结点。

void PostOrder(CSTree T) {//后根遍历
	if (T != NULL) {
		CSTree C = T->firstchild;
		do {
			PostOrder(C);//对以C为根的子树后根遍历
			C = C->nextsibling;//依次访问C的右兄弟结点
		} while (C != NULL);
		Visit(T);//最后访问根结点
	}
	return;
}

其遍历序列与这棵树对应二叉树的中序序列相同。
例如，前文中图$5.23$中的树，先根遍历序列为$ABEFCDG$，后根遍历序列为$EFBCGDA$。

3)层次遍历

基本思想与二叉树的层次遍历相同。首先构造辅助队列；根结点入队；队头元素出队，访问当前结点，再将该结点的所有孩子结点入队；依次类推，直到队列为空。

2. 森林的遍历

由于森林和树相互递归的定义，可以得到森林的两种遍历方法：

$1)$先序遍历森林。若森林非空，则按如下规则遍历：

• 先访问森林中第一棵树的根结点。
• 先序遍历第一棵树中根结点的子树森林。
• 先序遍历除去第一棵树之后剩余的树构成的森林。

其实就是按顺序对森林里每棵树依次进行先根遍历，然后把遍历序列按顺序连起来；或者把森林转换成二叉树再进行先序遍历。

$2)$中序遍历森林。若森林非空，则按如下规则遍历：

• 中序遍历第一棵树中根结点的子树森林。
• 访问森林中第一棵树的根结点。
• 中序遍历除去第一棵树之后剩余的树构成的森林。

其实就是按顺序对森林里每棵树依次进行后根遍历，然后把遍历序列按顺序连起来；或者把森林转换成二叉树再进行中序遍历。

对树的遍历，层次遍历又被称为广度优先遍历，先根、后跟又被称为深度优先遍历。
408考研初试中，需掌握手推树与森林的遍历序列的能力，如果运气太差碰到代码实现题，可以先转换成二叉树，再用熟悉的方法处理问题。
以上。