数据结构是计算机考研的重要内容之一，数据结构的核心考点较多，复习较困难。为了帮助大家更好的了解和复习备考，小编为大家整理了计算机考研数据结构高频考点：树和森林的遍历的详细内容，一起来看看吧。
2024计算机考研数据结构考点：树和森林的遍历
　　一、树的遍历
　　1.先根遍历
　　先访问根,再从左到右遍历每棵子树,与相应二叉树的先根遍历相同
　　2.后根遍历
　　从左到右遍历每棵子树,再访问根,与相应二叉树的中根遍历相同
　　3.层次遍历
　　（1）定义：
　　①若树非空，则根结点入队；
　　②若队列非空，则队头元素出队并访问，同时将该元素的孩子依次入队；
　　③重复②直到队列为空；
　　（2）层次遍历也称广度优先遍历；
　　（3）树的后根遍历序列与这棵树相应二叉树的中序序列相同。
　　二、森林的遍历
　　1.先序遍历
　　若森林为非空，则按如下规则进行遍历：
　　访问森林中第一棵树的根结点；
　　先序遍历第一棵树中根结点的子树森林。
　　继续先序遍历除去第一棵树之后剩余的树构成的森林。
　　效果等同于依次对各个树（二叉树）进行先根遍历。
　　2.中序遍历森林
　　若森林为非空，则按如下规则进行遍历：
　　中序遍历森林中第一棵树的根结点的子树森林；
　　访问第一棵树的根结点；
　　继续中序遍历除去第一棵树之后剩余的树构成的森林。
　　效果等同于依次对各个树进行后根遍历；
　　效果等同于依次对二叉树的中序遍历。
　　三、树,森林与二叉树的转换
　　树转换为二叉树：左指针指向第一个孩子,右指针指向第一个兄弟,根没有兄弟,二叉树没有右子树。
　　森林转换为二叉树：每棵二叉树的根依次作为上一颗二叉树的右子树。
　　二叉树转换为森林：二叉树的根及左子树作为第一棵树的二叉树形态,再转换为树(右孩子变为兄弟);根的右子树及其左孩子作为第二棵树,右孩子作为第三棵树,反复下去。
　　以上内容整理于网络，仅供参考。
　　以上就是学姐为大家整理的【2024计算机考研数据结构考点：树和森林的遍历】的全部内容！想了解更多关于考研的相关信息，请关注高顿考研官网查询，祝大家考研成功。另外，小编为2024考研的小伙伴们准备了丰富的学习资料，点击下方蓝色小卡片即可获取哦~
相关阅读
延伸阅读



展开全文