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

专项知识点4根据中序加后序推算二叉树中序遍历为：DHBEAIFCJGK后序遍历为：HDEBIFJKGCA（本文根据后序遍历从后往前逐位判定元素位置）第一步：判定根节点【因为后序遍历的遍历顺序为左右根，所以可以判定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的右边第