二叉树由两种遍历推出整棵树

r囧r小猫 2022-01-21 10:39 184阅读 0赞

### 二叉树由两种遍历推出整棵树 ###

二叉树的先序，中序，后序遍历中，任意知道两种就可以推出整棵树长什么样。思路都是一样的，这里以先序和中序为例。

以下这个过程涉及到逆向推导，请读者准备个草稿纸XD

例如：已知先序遍历和中序遍历，求整棵树的形状？  
先序：A B D E H C F I J G  
中序：D B H E A F J I C G

解：  
先序遍历的第一个元素是根节点，所以A为根节点，通过中序遍历中的A的位置，我们可以将中序遍历的左子树和右子树分出来：  
`D B H E` A `F J I C G`  
左子树 … … 右子树  
所以可以画出这样一个草图:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]

接下来我们再对左子树BDEH进行分析:  
先序：A B D E H `C F I J G`  
中序：D B H E A `F J I C G`  
所以对左子树来说，先序和中序分别是：  
先序：B D E H  
中序：D B H E  
所以同理B为根节点，分出左右子树:  
中序：`D` B `H E`  
其左子树为D右子树为HE  
进一步细化这个图得到：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]  
然后接着上面的继续：  
先序：B `D` E H  
中序：`D` B H E  
所以对右子树来说，先序和中序分别是：  
先序：E H  
中序：H E  
所以同理E为根节点，H为左子树。  
进一步细化这个图得到：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 2]  
现在的话，整个左边已经全部划分清楚了，现在来看右边部分：  
总的排序：  
先序：A `B D E H` C F I J G  
中序：`D B H E` A F J I C G  
所以对右子树来说，先序和中序分别是：  
先序：C F I J G  
中序：F J I C G  
所以同理C为根节点，分出左右子树:  
中序：`F J I` C `G`  
得到左子树FJI和右子树G，细分之后画图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 3]  
现在再来分析FJI这棵树:  
先序：F I J  
中序：F J I  
所以自然而然，根节点F。但这里注意以下，中序也是F在第一个位置，所以左子树为空，右子树为JI，所以右子树也像上面那样再划分一次，最后得到完整的树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 4]

成功！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220121/85752678a1ed4d36b7eaaac2451e92a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]: /images/20220121/9a974edd36d746018d0953de979fd042.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 2]: /images/20220121/d7aa33f222d442009b15f0eb266464af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 3]: /images/20220121/b329dc75a9af4920ba902eddf83fa222.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 4]: /images/20220121/6d81e1f69eca47a987daef49de6350f1.png