前序ADCEFGHB 中序CDFEGHAB求 后序
时间: 2024-04-25 09:19:46 浏览: 21
对于给定的前序遍历序列"ADCEFGHB"和中序遍历序列"CDFEGHAB",我们可以通过以下步骤来求解后序遍历序列:
1. 首先,我们可以观察到前序遍历序列的第一个元素是根节点,即"A"。然后我们在中序遍历序列中找到根节点的位置,将中序遍历序列分为左子树和右子树的部分。
2. 在中序遍历序列中,根节点的左边是左子树的节点,根节点的右边是右子树的节点。根据这个划分,我们可以得到左子树的中序遍历序列为"CDFE",右子树的中序遍历序列为"GHA"。
3. 接下来,我们需要确定左子树和右子树的前序遍历序列。根据前序遍历的性质,左子树的前序遍历序列为除去第一个元素(即根节点)后的前序遍历序列,即"DCEFGH";右子树的前序遍历序列为从左子树的最后一个节点之后开始的剩余部分,即"B"。
4. 现在,我们可以递归地应用上述步骤来求解左子树和右子树的后序遍历序列。对于左子树,左子树的前序遍历序列为"DCEFGH",中序遍历序列为"CDFE",可以得到左子树的后序遍历序列为"CFEDHG";对于右子树,右子树的前序遍历序列为"B",中序遍历序列为"GHA",可以得到右子树的后序遍历序列为"GHA"。
5. 最后,我们将左子树的后序遍历序列和右子树的后序遍历序列拼接在一起,并将根节点的值添加到最后,即得到整棵树的后序遍历序列为"CFEDHGBA"。
所以,给定前序遍历序列"ADCEFGHB"和中序遍历序列"CDFEGHAB",其对应的后序遍历序列为"CFEDHGBA"。
相关问题
通过前序遍历和中序遍历求后序遍历
通过前序遍历和中序遍历求后序遍历的方法如下:
1. 首先,我们知道前序遍历的特点是先访问根节点,然后遍历左子树,最后遍历右子树。而中序遍历的特点是先遍历左子树,然后访问根节点,最后遍历右子树。
2. 根据这两种遍历的特点,我们可以确定根节点的位置。在前序遍历中,第一个节点就是根节点;而在中序遍历中,根节点的位置是在左子树的节点之后。
3. 接下来,我们可以将前序遍历和中序遍历分为左子树和右子树两部分。左子树的节点在前序遍历和中序遍历中都是连续的,右子树的节点在前序遍历和中序遍历中也是连续的。
4. 根据左子树和右子树的节点数目,我们可以将前序遍历和中序遍历进一步分割成更小的部分。对于左子树,我们可以再次使用前序遍历和中序遍历求解后序遍历;同样地,对于右子树也是如此。
5. 重复上述步骤,直到只剩下一个节点。此时,我们就得到了整颗二叉树的后序遍历序列。
所以通过前序遍历和中序遍历可以求得后序遍历。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [二叉树前序、中序、后序遍历相互求法](https://blog.csdn.net/liuchen1206/article/details/8542996)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [已知先序遍历序列和中序遍历序列,求后序遍历序列](https://blog.csdn.net/qq_40685275/article/details/100177830)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
递归的前序,中序,后序与非递归的前序,中序,后序
递归的前序、中序和后序遍历是二叉树遍历的常用方法。其中,前序遍历先访问根节点,然后访问左子树,最后访问右子树;中序遍历先访问左子树,然后访问根节点,最后访问右子树;后序遍历先访问左子树,然后访问右子树,最后访问根节点。
非递归的前序、中序和后序遍历也是二叉树遍历的常用方法。其中,非递归的前序遍历需要使用栈来实现,具体过程为:将根节点压入栈中,循环执行以下操作直到栈为空:弹出栈顶元素并访问,若其右子节点不为空,则将右子节点压入栈中;若其左子节点不为空,则将左子节点压入栈中。非递归的中序遍历与非递归的前序遍历类似,只是在弹出栈顶元素并访问之后再将其右子节点压入栈中。非递归的后序遍历需要使用两个栈来实现,具体过程为:将根节点压入第一个栈中,循环执行以下操作直到第一个栈为空:弹出第一个栈顶元素并压入第二个栈中,若其左子节点不为空,则将左子节点压入第一个栈中;若其右子节点不为空,则将右子节点压入第一个栈中。最后,依次弹出第二个栈的元素并访问即可得到非递归的后序遍历结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c++](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)