前序ADCEFGHB 中序CDFEGHAB求 后序
时间: 2024-04-25 12:19:46 浏览: 68
前序中序求后序
对于给定的前序遍历序列"ADCEFGHB"和中序遍历序列"CDFEGHAB",我们可以通过以下步骤来求解后序遍历序列:
1. 首先,我们可以观察到前序遍历序列的第一个元素是根节点,即"A"。然后我们在中序遍历序列中找到根节点的位置,将中序遍历序列分为左子树和右子树的部分。
2. 在中序遍历序列中,根节点的左边是左子树的节点,根节点的右边是右子树的节点。根据这个划分,我们可以得到左子树的中序遍历序列为"CDFE",右子树的中序遍历序列为"GHA"。
3. 接下来,我们需要确定左子树和右子树的前序遍历序列。根据前序遍历的性质,左子树的前序遍历序列为除去第一个元素(即根节点)后的前序遍历序列,即"DCEFGH";右子树的前序遍历序列为从左子树的最后一个节点之后开始的剩余部分,即"B"。
4. 现在,我们可以递归地应用上述步骤来求解左子树和右子树的后序遍历序列。对于左子树,左子树的前序遍历序列为"DCEFGH",中序遍历序列为"CDFE",可以得到左子树的后序遍历序列为"CFEDHG";对于右子树,右子树的前序遍历序列为"B",中序遍历序列为"GHA",可以得到右子树的后序遍历序列为"GHA"。
5. 最后,我们将左子树的后序遍历序列和右子树的后序遍历序列拼接在一起,并将根节点的值添加到最后,即得到整棵树的后序遍历序列为"CFEDHGBA"。
所以,给定前序遍历序列"ADCEFGHB"和中序遍历序列"CDFEGHAB",其对应的后序遍历序列为"CFEDHGBA"。
阅读全文