专项知识点3 二叉树推算（前序、中序）知识点梳理—2024届高考信息技术二轮复习知识点梳理

专项知识点3 根据前序加中序推算二叉树 前序遍历为：A-B-D-H-E-C-F-I-G-J-K 中序遍历为：D-H-B-E-A-I-F-C-J-G-K （本文根据前序遍历从前往后逐位判定元素位置） 第一步：判定根节点【因为前序遍历的遍历顺序为根左右，所以可以判定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.10 第十二步：判定K的位置【根据第十步的结果，因为中序遍历K在G的右边，说明K是G的右子树】可以绘制如下二叉树图 图1.11 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$