专项知识点3二叉树推算（前序中序）知识点梳理高考信息技术二轮复习知识点梳理_第1页
专项知识点3二叉树推算（前序中序）知识点梳理高考信息技术二轮复习知识点梳理_第2页
专项知识点3二叉树推算（前序中序）知识点梳理高考信息技术二轮复习知识点梳理_第3页
专项知识点3二叉树推算（前序中序）知识点梳理高考信息技术二轮复习知识点梳理_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

专项知识点3根据前序加中序推算二叉树前序遍历为：ABDHECFIGJK中序遍历为：DHBEAIFCJGK（本文根据前序遍历从前往后逐位判定元素位置）第一步：判定根节点【因为前序遍历的遍历顺序为根左右，所以可以判定A为整棵树的根节点】，可以绘制如下二叉树图图1.1第二步：判定A的左右子树范围【因为中序遍历的遍历顺序为左根右，所以可以判定DHBE是A的左子树，IFCJGK为A的右子树】第三步：判定B的位置【前序遍历的顺序是根左右，观察前序遍历可以得到B在A的右边第一个位置，所以可以初步判定B是A的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到B在A的左边，所以可以判定B是A的左子树】可以绘制如下二叉树图图1.2第四步：判定D的位置【前序遍历的顺序是根左右，观察前序遍历可以得到D在B的右边第一个位置，所以可以初步判定D是B的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到D在B的左边，所以可以判定D是B的左子树】可以绘制如下二叉树图图1.3第五步：判定H的位置【前序遍历的顺序是根左右，观察前序遍历可以得到H在D的右边第一个位置，所以可以初步判定H是D的右子树，中序遍历的顺序是左根右，观察中序遍历可以得到H在D的右边第一个位置，所以可以判定H是D的右子树】可以绘制如下二叉树图图1.4第六步：判定E的位置【基于前五步推出的结果，因为中序遍历E在B的右边，所以可以判定E是B的右子树】可以绘制如下二叉树图图1.5第七步：判定C的位置【观察中序遍历可以得到A是根节点，C在A的右边，据此可以判定C是A的右边子树，又根据前序遍历C在右边子树的第一个位置，因为前序遍历是根左右，所以可以判定C是A的右子树】可以绘制如下二叉树图图1.6第八步：判定F的位置【前序遍历的顺序是根左右，观察前序遍历可以得到F在C的右边第一个，可以初步判定F是C的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到F在C的左边，所以可以判定F是C的左子树】可以绘制如下二叉树图图1.7第九步：判定I的位置【前序遍历的顺序是根左右，观察前序遍历可以得到I在F的右边第一个位置，可以初步判定I是F的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到I在F的左边第一个位置，所以可以判定I是F的左子树】可以绘制如下二叉树图图1.8第十步：判定G的位置【观察前序遍历G在I的右边第一个位置，但是中序遍历G和I并不是相邻关系，所以可以判定G并不是I的子树，此时根据遍历原理，需要去判定G是不是C的子树，观察中序遍历可得JGK都在C的右边，说明JGK都是C的右子树，又根据前序遍历和中序遍历的顺序，可以得到G是JGK的根节点也是C的右子树】可以绘制如下二叉树图图1.9第十一步：判定J的位置【根据第十步的结果，因为中序遍历J在G的左边，说明J是G的左子树】可以绘制如下二叉树图图1

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论