全国计算机二级公共基础知识考试重点(五)

全国计算机二级公共基础知识考试重点(五)

二叉树的遍历

二叉树的遍历即是不重复地访问二叉树的所有结点。

在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。

1)前序遍历

前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。

操作的具体方式：

若二叉树为空，则结束返回。

否则：访问根结点前序遍历左子树前序遍历右子树

如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O

2)中序遍历

中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。

具体的操作方式：

若二叉树为空，则结束返回。

否则：中序遍历左子树访问根结点 中序遍历右子树

这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。

如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O

3)后序遍历

后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。

具体的操作方式：

若二叉树为空，则结束返回。

否则：前序遍历左子树前序遍历右子树访问根结点

如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A

以上内容为全国计算机二级公共基础知识考试重点(五)，希望对备战二级公共基础知识的同学有所帮助。担心错过准考证打印时间，来用环球网校“ 免费预约短信提醒”及时得到考试时间提醒吧!此外，环球网校友情提示：在备战计算机二级考试中，环球网校特地为您准备了计算机二级复习资料，如有需要请点击文章下方“免费下载>>>计算机二级考试资料”下载学习。