由遍历序列确定二叉树

ゞ浴缸里的玫瑰 2022-03-21 04:04 166阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>两种遍历序列的组合</th> 
   <th>能否唯一确定二叉树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>先序+中序</td> 
   <td>能</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>后序+中序</td> 
   <td>能</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>先序+后序</td> 
   <td>否</td> 
  </tr> 
 </tbody> 
</table>

已知一棵树的两种序列，如何构造该二叉树  
例：已知一棵树的先序和中序序列分别为：  
A B C D E F G H I  
B C A E D G H F I  
试构造该二叉树  
答：思路：  
首先看先序序列：先序序列先看根，再看左子树、右子树，那么A就是该二叉树的根；然后，看中序序列，中序序列先看左子树，再看根，再看右子树，B C 在A 前头，而且A又是根，那么B C 就是属于左子树，D E F G H I 就是属于右子树。

其次看左子树：在先序序列中，左子树先访问的是B，然后再是C，那么，B 就是左子树的根；再看中序序列，左子树先访问的也是B，然后再是C，那么C就是B 的右子树

然后再看右子树：在先序序列中，右子树先访问的是D，那么D就是右子树的根，再看中序序列，先访问的是E，然后再是D，那么，E就是右子树下的左子树，F G H I 就是右子树下的右子树。

最后看右子树下的右子树（F G H I）：在先序序列中，先访问的是F，那么F就是该分支树的根，再看中序序列，F前面是G H ,后面是I，则G H是分支树下的左子树，I是分支树下的右子树；又 (F G H ),(G H F)与（A B C),(B C A)一样，所以G 是分支根，H 是其右子树。

画出如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fYmVpXw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fYmVpXw_size_16_color_FFFFFF_t_70]: /images/20220321/1ec2b4e15bb04192aca24f911d8e207c.png