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

专项知识点4 根据中序加后序推算二叉树 中序遍历为：D-H-B-E-A-I-F-C-J-G-K 后序遍历为：H-D-E-B-I-F-J-K-G-C-A （本文根据后序遍历从后往前逐位判定元素位置） 第一步：判定根节点【因为后序遍历的遍历顺序为左右根，所以可以判定A为整棵树的根节点】，可以绘制如下二叉树图 图1.1 第二步：判定A的左右子树范围【因为中序遍历的遍历顺序为左根右，所以可以判定DHBE是A的左子树，IFCJGK为A的右子树】 第三步：判定C的位置【后序遍历的顺序是左右根，观察后序遍历可以得到C在A的左边第一个位置，所以可以初步判定C是A的右子树，中序遍历的顺序是左根右，观察中序遍历可以得到C在A的右边，所以可以判定C是A的右子树】可以绘制如下二叉树图 图1.2 第四步：判定G的位置【后序遍历的顺序是左右根，观察后序遍历可以得到G在C的左边第一个位置，所以可以初步判定G是C的右子树，中序遍历的顺序是左根右，观察中序遍历可以得到G在C的右边，所以可以判定G是C的右子树】可以绘制如下二叉树图 图1.3 第五步：判定K的位置【后序遍历的顺序是左右根，观察后序遍历可以得到K在G的左边第一个位置，所以可以初步判定K是G的右子树，中序遍历的顺序是左根右，观察中序遍历可以得到K在G的右边，所以可以判定K是G的右子树】可以绘制如下二叉树图 图1.4 第六步：判定J的位置【后序遍历的顺序是左右根，观察后序遍历可以得到J在K的左边第一个位置，且根据上一步推的K是G的右子树，此时可以初步判定J是G的左子树，又因为中序遍历的顺序是左根右，观察中序遍历可以得到J在G的左边，所以可以判定J是G的左子树】可以绘制如下二叉树图 图1.5 第七步：判定F的位置【根据前六步的结果，可以得到F只能是C的左子树（观察中序遍历，因为F在C的左边第一个位置）】可以绘制如下二叉树图 图1.6 第八步：判定I的位置【后序遍历的顺序是左右根，观察后序遍历可以得到I在F的左边第一个位置，所以可以初步判定I是F的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到I在F的左边第一个位置，所以可以判定I是F的左子树】可以绘制如下二叉树图 图1.7 第九步：判定B的位置【中序遍历的顺序是左根右，已知A是根节点，所以B必定是A的左边子树，后序遍历中B在左边子树的最后一个位置，因为后序遍历的顺序是左右根，所以可以判定B是左边子树的根，也就是A的左子树】可以绘制如下二叉树图 图1.8 第十步：判定E的位置【中序遍历的顺序是左根右，观察中序遍历可以得到E在B的右边第一个位置，因为上一步推的B是根节点，所以可以初步判定E是B的右子树，后序遍历的顺序是左右根，观察后序遍历可以得到E在B的左边第一个位置，所以可以判定E是B的右子树】可以绘制如下二叉树图 图1.9 第十一步：判定D的位置【后序遍历的顺序是左右根，观察后序遍历可以得到D在E的左边第一个位置，因为上一步推的E是右节点，所以可以初步判定D是B的左子树，中序遍历的顺序是左根右，观察中序遍历可以得到D在B的左边，所以可以判定D是B的左子树】可以绘制如下二叉树图 图1.10 第十二步：判定H的位置【中序遍历的顺序是左根右，因为B的子树已经满了，所以只能是B的子树的子树，观察后序遍历，因为H在D的右边第一个位置，所以可以初步判定H是D的右子树，中序遍历H在D的右边，根据中序遍历的原理，可以判定H是D的右子树】可以绘制如下二叉树图 图1.11 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$