计算机考研专业课，很多学校以408为主!接下来，小编为帮助备考2023计算机考研408的学子们，在头脑中有一个专业课思维框架，特意精心为大家整理出-计算机考研408数据结构知识:树和森林，供考生参考。
2023计算机考研408数据结构知识:树和森林
一、树的存储结构
1.双亲表示法
定义: 连续空间存储,每个结点增设一个伪指针,指示双亲在数组中位置,根结点下标为0,其伪指针为-1
特点: 可以很快得到双亲,但求孩子要遍历整个结构
2.孩子表示法
定义: 将每个结点的孩子用单链表连成线性结构
特点: 求孩子很方便,求双亲不方便
3.孩子兄弟表示法(左孩子右兄弟)
定义: 左指针指向第一个孩子,右指针指向第一个兄弟,二叉链表作为存储结构
优点: 方便实现树转化为二叉树,易于查找孩子
缺点: 查找双亲麻烦,若增设parent指向双亲,会方便
二、树,森林与二叉树的转换
树转换为二叉树：左指针指向第一个孩子,右指针指向第一个兄弟,根没有兄弟,二叉树没有右子树
森林转换为二叉树：每棵二叉树的根依次作为上一颗二叉树的右子树
二叉树转换为森林：二叉树的根及左子树作为第一棵树的二叉树形态,再转换为树(右孩子变为兄弟);根的右子树及其左孩子作为第二棵树,右孩子作为第三棵树,反复下去
三、树和森林的遍历
树的先根遍历：先访问根,再从左到右遍历每棵子树,与相应二叉树的先根遍历相同
树的后根遍历：从左到右遍历每棵子树,再访问根,与相应二叉树的中根遍历相同
先序遍历森林：与二叉树先根遍历同
中序遍历森林：与二叉树中根遍历同
四、树的应用——并查集
1.3种操作
Union(S,Root1,Root2): 合并两个子集合,将根Root2连接到根Root1下，S[Root2]=Root1
Find(S,x): 查找包含x的树的根,直到找到负数为止，while(s[x]>=0) x=S[x];return x;
Inital(s): 集合S中每个元素初始化为只有单元素的子集合(所有元素赋值为-1)
2.存储结构: 树的双亲表示法,根结点下标为子集合名,根结点的双亲结点为负数,大小为子集合结点数量
综上是“2023计算机考研408数据结构知识:树和森林”，希望对计算机考研者们有所帮助!世界上唯一可以不劳而获的就是贫穷，唯一可以无中生有的是梦想。没有哪件事，不动手就可以实现。世界虽然残酷，但只要你愿意走，总会有路;看不到美好，是因为你没有坚持走下去。人生贵在行动，迟疑不决时，不妨先迈出小小一步。前进不必遗憾，若是美好，叫做精彩;若是糟糕，叫做经历!加油!
