由遍历序列确定二叉树--数据结构

桃扇骨 2022-11-21 03:50 164阅读 0赞

### 由遍历序列确定二叉树 ###

*   *   *   *  1.由先序和中序序列确定二叉树
             *  2.由中序和后序序列确定二叉树

由二又树的遍历可知，任意一棵二又树的先序、中序、后序遍历序列均是唯一的。  
由先序和中序序列，或由中序和后序序列,均可以唯一确定一棵二叉树。（**注意：由先序和后序无法确定一颗二叉树**）

#### 1.由先序和中序序列确定二叉树 ####

根据二叉树遍历的定义可知，二叉树的 ***先序遍历是先访问根结点D,其次遍历左子树L,最后遍历右子树R,*** 即在先序序列中,第一个结点必是根D;  
而另一方面,由于 ***中序遍历是先遍历左子树L,其次访问根D,最后遍历右子树R,*** 即在中序序列中，根结点前是左子树序列，后是右子树序列。因此，由先序和中序序列确定二又树的方法如下：

①由先序序列中的第一个结点确定根结点D。  
②由根结点D分割中序序列:D之前是左子树上的中序序列.D之后是右子树R的中序序列,同时获得L和R的结点个数。  
③根据左子树L的结点个数,分割先序序列:第一结点根D，之后是左子树L的先序序列，最后是右子树R的先序序列。

至此,已确定了根D,左子树L的先序和中序序列,右子树R的先序和中序序列。如此类推,再对每棵子树进行上述处理,便可确定整棵二叉树。

**个人理解：**

> 第一步：首先根据先序序列确定根结点，再由确立的根结点分割中序序列，确立根结点左右子树的结点；  
> 第二步：确立根结点左右子树的结点之后，先看左子树的结点在先序序列中谁更靠前（***最靠前的为该层的左节点***），再看右子树的结点在先序序列中谁更靠前（***最靠前的为该层的右节点***）；  
> 第三步：在第二步确立了左右结点后，先由左结点分割中序序列，确立左结点以下的左右结点，再由右结点分割中序序列，确立右结点以下的左右结点。  
> 第四步：确立左右结点左右子树的结点之后，先看左子树的结点在先序序列中谁更靠前（***最靠前的为该层的左节点***），再看右子树的结点在先序序列中谁更靠前（***最靠前的为该层的右节点***）；  
> …(重复第三步第四步)

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center]

#### 2.由中序和后序序列确定二叉树 ####

类似于上述由先序和中序序列确定二叉树的方法,可得到由中序和后序序列确定二叉树的方法如下:  
①由后序序列中的最后一个结点确定根结点D；  
②由根结点D分割中序序列:D之前是左子树L的中序序列,D之后是右子树R的中序序列,同时获得L和R的结点个数。  
③根据左子树L的结点个数分割后序序列:首先是左子树L的  
后序序列,随后是右子树R的后序序列,最后是根结点D。

至此,已确定了根D,左子树L的中序和后序序列,右子树R的中序和后序序列。如此类推,再对每棵子树进行上述处理，便可确定整棵二叉树。

总体来说，数据结构需要自己慢慢理解，而不是一蹴而就，自己对它的理解还仅仅停留在栈中，要好好努力了，fighting!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0649fde63a1047b2afabbb53182b5de7.png