数据结构 --树和森林

树和森林

树的存储结构

树的逻辑结构

树是一种递归定义的数据结构

树是n(n≥0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1)有且仅有一个特定的称为根的结点。

2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2…,Tm,其中每个集合本身又是一棵树，并且称为根的子树。

二叉树：每个分支节点最多只有两棵子树

树：一个分支节点可以有多颗子树

对于一颗普通的树只依靠数组下标，无法反映节点之间的逻辑关系

双亲表示法（顺序存储）

基于树的特点：除了根结点，每个结点有且只有一个双亲（父节点）

//树的存储 -- 双亲表示法
#define MAX_TREE_SIZE 100			//树中最多结点数
typedef struct{						//树的结点定义ElemType data;					//数据元素int parent;						//双亲位置域
}PTNode;
typedef struct{						//树的类型表示PTNode nodes[MAX_TREE_SIZE];	//双亲表示int n;			//结点数
}

【拓展】双亲表示法也可以用于存储“森林”

【优缺点】

优点：找双亲（父节点）很方便

缺点：找孩子不方便，只能从头到尾遍历整个数组

适用于找“父亲多”，找“孩子”少的场景。如：并查集

孩子表示法（顺序存储+链式存储）

用数组顺序存储各个节点。每个节点中保存数据元素、孩子链表头指针（顺序存储+链式存储结合）

//树的存储 -- 孩子表示法
struct CNode{int child;	//孩子结点在数组中的位置struct CNode *next;		//下一个孩子
}
typedef struct{ElemType data;struct CNode *firstChild;	//第一个孩子
}CTBox;
typedef struct{CTBox nodes[MAX_TREE_SIZE];int n,r;		//结点数和根的位置
}CTree;

【拓展】孩子表示法也可以用于存储“森林”

如果使用孩子表示法存储森林，需要记录多个根的位置

【优缺点】

优点：找孩子很方便

缺点：找双亲（父节点）不方便，只能遍历每个链表

适用于找“孩子”多，找“父亲”少的场景。如：服务流程树

孩子兄弟表示法（链式存储）

//树的存储 -- 孩子兄弟表示法（左孩子右兄弟）
typedef struct CSNode{ElemType data;							//数据域struct CSNode *firstchild,*nextsibling;	//第一个孩子和右兄弟指针
}CSNode,*CSTree;

从存储视角来看形态上与二叉树类似

【拓展】双亲表示法也可以用于存储“森林”

用于存储森林时，将森林中的每一棵树的根结点视为平级的兄弟关系

树、森林与二叉树之间的转换

树→二叉树的转换（孩子兄弟表示法）

技巧：

①现在二叉树中，画一个根结点

②按“树的层序”依次处理每个节点

处理一个结点的方法是：如果当前处理的结点中在树中右孩子，就把所有孩子节点“用右指针串在一起”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

森林→二叉树的转化（孩子兄弟表示法）

技巧：

①先把所有树的根结点画出来，在二叉树中用右指针串起来

②按“森林的层序”依次处理每个节点

处理一个结点的方法是：如果当前处理的结点中在树中右孩子，就把所有孩子节点“用右指针串在一起”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

二叉树→树的转换

技巧：

①先画出树的根结点

②从树的根结点开始，按“树的层序”恢复每个结点的孩子

恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“用右指针与根结点相连的一整串”拆下来，按顺序挂在当前节点的下方

二叉树→森林的转换

技巧：

①先把二叉树的根结点和“用右指针与根结点相连的一整串”拆下来，作为多棵树的根结点

②按“森林的层序”恢复每个结点的孩子

恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“用右指针与根节点相连的一整串”拆下来，按顺序挂在当前节点的下方

树、森林的遍历

树的遍历

先根遍历（深度优先遍历）

若树非空，先访问根结点，再依次对每颗子树进行先根遍历。

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

//树的先根遍历（伪代码）
void PreOrder(TreeNode *R){if(R!=NULL){visit(R);	//访问根节点while(R还有下一个子树T)PreOrder(T);}
}

后根遍历（深度优先遍历）

若树非空，先依次对每颗子树进行后根遍历，再访问根结点。

树的后根遍历序列与这棵树相对应的二叉树的中序序列相同

void PostOrder(TreeNode *R){if(R != NULL){while(R还有下一个子树T)PostOrder(T);	//后根遍历下一棵子树visit(R);		//访问根结点}
}

层序遍历（广度优先遍历）

（需要利用队列实现）

① 若树非空，则根节点入队

② 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③ 重复②直到队列为空

森林的遍历

先序遍历

若森林非空，则按以下规则进行遍历：

① 访问森林中第一棵子树的根结点

② 先序遍历第一棵树中根结点的子树森林

③ 先序遍历除去第一颗树之后剩余的树构成的森林

效果等同于依次对各个树进行先根遍历

效果等同于对与这片森林对应的二叉树进行先序遍历

中序遍历

若森林非空，则按以下规则进行遍历：

① 中序遍历森林中第一棵树的根节点的子树森林

② 访问第一棵树的根结点

③ 中序遍历除去第一颗树之后剩余的树构成的森林

效果等同于依次对各个树进行后根遍历

效果等同于对与这片森林对应的二叉树进行中序遍历

[!TIP]

如果考试考到森林的相关代码题目，可以把森林转化成二叉树，然后对二叉树进行遍历