2024年计算机考研必背知识点：树和森林的遍历

        计算机考研必背知识点有很多，树和森林的遍历需要考生了解树的遍历、森林的遍历、树、森林与二叉树的转换等基本内容。为了帮助考生们了解计算机考研必背知识点，高顿小编为大家整理出一些基本情况，一起来了解下吧！

　　一、树的遍历
　　1.先根遍历
　　先访问根,再从左到右遍历每棵子树,与相应二叉树的先根遍历相同
　　2.后根遍历
　　从左到右遍历每棵子树,再访问根,与相应二叉树的中根遍历相同
　　3.层次遍历
　　（1）定义：
　　①若树非空，则根结点入队；
　　②若队列非空，则队头元素出队并访问，同时将该元素的孩子依次入队；
　　③重复②直到队列为空；
　　（2）层次遍历也称广度优先遍历；
　　（3）树的后根遍历序列与这棵树相应二叉树的中序序列相同。
　　二、森林的遍历
　　1.先序遍历
　　若森林为非空，则按如下规则进行遍历：
　　访问森林中第一棵树的根结点；
　　先序遍历第一棵树中根结点的子树森林。
　　继续先序遍历除去第一棵树之后剩余的树构成的森林。
　　效果等同于依次对各个树（二叉树）进行先根遍历。
　　2.中序遍历森林
　　若森林为非空，则按如下规则进行遍历：
　　中序遍历森林中第一棵树的根结点的子树森林；
　　访问第一棵树的根结点；
　　继续中序遍历除去第一棵树之后剩余的树构成的森林。
　　效果等同于依次对各个树进行后根遍历；
　　效果等同于依次对二叉树的中序遍历。
　　三、树,森林与二叉树的转换
　　树转换为二叉树：左指针指向第一个孩子,右指针指向第一个兄弟,根没有兄弟,二叉树没有右子树。
　　森林转换为二叉树：每棵二叉树的根依次作为上一颗二叉树的右子树。
　　二叉树转换为森林：二叉树的根及左子树作为第一棵树的二叉树形态,再转换为树(右孩子变为兄弟);根的右子树及其左孩子作为第二棵树,右孩子作为第三棵树,反复下去。
　　以上内容来源网络，仅供参考！
　　以上是小编整理的关于【2024年计算机考研必背知识点：树和森林的遍历】的全部内容，如果想要了解更多关于院校选择、专业选取、就业问题等，可直接点击下方咨询，由专业老师为您一对一解答！