根据前序遍历和中序遍历求后序遍历

逃离我推掉我的手 2021-12-03 05:07 274阅读 0赞

假设某二叉树的先序遍历序列是abdgcefh，[中序遍历][Link 1]序列是dgbaechf，画出二叉树，并给出其[后序遍历][Link 2]序列。  
分析过程：  
以下面的[例题][Link 3]为例进行讲解：  
已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf，求二叉树及后序遍历序列。  
分析：先序遍历序列的第一个[字符][Link 4]为[根结点][Link 5]。对于中序遍历，根结点在中序遍历序列的[中间][Link 6]，[左边][Link 7]部分是根结点的[左子][Link 8]树的中序遍历序列，[右边][Link 9]部分是根结点的[右子][Link 10]树的中序遍历序列。  
先序：abdgcefh --> a bdg cefh  
中序：dgbaechf --> dgb a echf  
得出结论：a是树根，a有左子树和右子树，左子树有bdg[结点][Link 11]，右子树有cefh结点。  
先序：bdg --> b dg  
中序：dgb --> dg b  
得出结论：b是左子树的根结点，b无右子树，有左子树。  
先序：dg --> d g  
中序：dg --> d g  
得出结论：d是b的左子树的根结点，d无左子树，有右子树。  
先序：cefh --> c e fh  
中序：echf --> e c hf  
得出结论：c是右子树的根结点，c有左子树(只有e结点)，有右子树(有fh结点)。  
先序：fh --> f h  
中序：hf --> h f  
得出结论：f是c的右子树的根结点，f有左子树(只有h结点)，无右子树。  
还原二叉树为：  
a  
b c  
d e f  
g h  
后序遍历序列：gdbehfca

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][]

[Link 1]: http://www.so.com/s?q=%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86&ie=utf-8&src=internal_wenda_recommend_textn
[Link 2]: http://www.so.com/s?q=%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86&ie=utf-8&src=internal_wenda_recommend_textn
[Link 3]: http://www.so.com/s?q=%E4%BE%8B%E9%A2%98&ie=utf-8&src=internal_wenda_recommend_textn
[Link 4]: http://www.so.com/s?q=%E5%AD%97%E7%AC%A6&ie=utf-8&src=internal_wenda_recommend_textn
[Link 5]: http://www.so.com/s?q=%E6%A0%B9%E7%BB%93%E7%82%B9&ie=utf-8&src=internal_wenda_recommend_textn
[Link 6]: http://www.so.com/s?q=%E4%B8%AD%E9%97%B4&ie=utf-8&src=internal_wenda_recommend_textn
[Link 7]: http://www.so.com/s?q=%E5%B7%A6%E8%BE%B9&ie=utf-8&src=internal_wenda_recommend_textn
[Link 8]: http://www.so.com/s?q=%E5%B7%A6%E5%AD%90&ie=utf-8&src=internal_wenda_recommend_textn
[Link 9]: http://www.so.com/s?q=%E5%8F%B3%E8%BE%B9&ie=utf-8&src=internal_wenda_recommend_textn
[Link 10]: http://www.so.com/s?q=%E5%8F%B3%E5%AD%90&ie=utf-8&src=internal_wenda_recommend_textn
[Link 11]: http://www.so.com/s?q=%E7%BB%93%E7%82%B9&ie=utf-8&src=internal_wenda_recommend_textn
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70]: /images/20211203/27556065b0054f62a44d71895c67fd75.png