已知一棵树二叉树的后根遍历和中根遍历的序列写出它的先根序列或者已知一棵树二叉树的先根遍历和中根遍历的序列写出它的后根序列

喜欢ヅ旅行 2023-09-29 09:27 22阅读 0赞

## **题一：** ##

**已知一棵树二叉树的 后根遍历 和 中根遍历 的序列分别为: ACDBGIHFE 和 ABCDEFGHI，**

**请画出该二叉树,并写出它的先根遍历的序列**

## **答：**   ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_15_color_FFFFFF_t_70_g_se_x_16][] ##

### 先根遍历序列：EBADCFHGI ###

## 解题思路： ##

**我们先找到根**

**后根：左 右 根  中跟：左 根 右**

**ACDB  GIHF E ABCD  E  FGHI**

我们先从后根去找，这个根一定是在这个遍历的后面，我们就可以确定E是根

然后我们在中根遍历中找到E的位置，所以E的左边就是左指数节点，右边是右指数节点

现在最上面的数E确定了，那谁是E左指数上的根呢，谁在后面谁是根：是B

然后再看中根遍历，谁在B的左边谁是左指数：是A；于是:

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_9_color_FFFFFF_t_70_g_se_x_16][]

现在在左指数上只有C和D没有画出来，

看中根遍历得到：C和D在B的右边，看后根遍历知道D在后面，所以D是根，

在中根遍历中，C在D的左边，所以C是D的左指数；

于是：以E为根节点的左指数画完

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_10_color_FFFFFF_t_70_g_se_x_16][]

接下来看看以E为根节点的右指数，先在后根遍历中找根节点，谁在后面谁是根节点：是F

再到中根遍历中找到F位置，F左边画完了，所以没有左指数，再看右边：GHI

回到后根遍历看GHI，得知H是根节点，所以：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_13_color_FFFFFF_t_70_g_se_x_16][]

现在只剩G、I 没有画了，所以回到中根遍历中看到G在H左，I 在H右，所以：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_15_color_FFFFFF_t_70_g_se_x_16][]

如果想知道画的对不对，带进题干，看看他的后根遍历和中根遍历对不对就行了

## **题二：** ##

**已知一棵树二叉树的先根遍历和中根遍历的序列分别为:ABDGHCEFI和GDHBAECIF，**

**请画出此二叉树，并写出它的后根遍的序列**

**构造的二叉树如下**  
![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_18_color_FFFFFF_t_70_g_se_x_16][]

### **后根遍历序列: GHDBEIFCA** ###

**解题思路：**  
**首先先找根**

**先根： 根 左 右  中根： 左 根 右**

**A BDGH CEFI   GDHB A ECIF**

看先根遍历得知A是根，然后在中根遍历中找到A的位置

所以得知GDHB在A的左边，ECIF在A的右边

那GDHB是谁根呢？回到先根遍历中，谁在前面谁是根，得知是B

再看中根，GDH在B的左边，那就是B的左指数

那GDH种谁是根呢？看先根中，D在前，那D就是根

再去中根遍历中找D的位置，得知左是G，右是H

现在以A为根节点的左指数已全部找到，那右指数就是ECIF

回到先根遍历中，那这四个谁在前面谁是根，是C

再去中根遍历中找C的位置，E在C的左边（左指数），I F在C的右边（右指数）

那 I F谁是根呢？去先根遍历中找：F在前，F是根

中根遍历中 I 在 F 左，于是 I 是F的左指数

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/20a243eddc4045efa692e26a95f47f7f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_9_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0531ac28b1fa4e67937738504ce88fe0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_9,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_10_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ed605af4db66465b839b452e3c0003e3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_10,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f3ee3e93ab424c94b4668bb3d77f2bfb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/69610ca0bd344b659499ca67607a51f7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_18,color_FFFFFF,t_70,g_se,x_16