[树] 二叉树、树、森林遍历问题 | 树的中序遍历问题

叁歲伎倆 2023-08-17 17:43 137阅读 0赞

### 文章目录 ###

*  \[总结\] 二叉树、树、森林三者遍历比较
 *  树的中序遍历问题

# \[总结\] 二叉树、树、森林三者遍历比较 #

【三种遍历方法对比】

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>二叉树</th> 
   <th>树</th> 
   <th>森林</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>先序遍历</td> 
   <td>第一次经过该结点就访问</td> 
   <td>根访问在前，先访问根结点，后访问其他结点</td> 
   <td>从左到右对森林中的每一棵树进行【先根遍历】</td> 
  </tr> 
  <tr> 
   <td>中序遍历</td> 
   <td>第二次经过结点的时候访问</td> 
   <td>树的度不一定，一般不说中序遍历，但非要谈，那就是<strong>第二次经过该结点时进行访问</strong></td> 
   <td>森林的中序、后序，只是许多地方说法不一样，实则是一个东西</td> 
  </tr> 
  <tr> 
   <td>后序遍历</td> 
   <td>第三次经过结点的时间访问</td> 
   <td>先遍历子树，再访问根结点（先访问子树是空的结点）</td> 
   <td>从左到右对森林中的每一棵树进行【后根遍历】</td> 
  </tr> 
 </tbody> 
</table>

【树、森林用二叉链表的形式存储（二叉链表的形式）时，其遍历对应着二叉树的遍历方式是什么？】

*  若树是用二叉链表的形式存储，那么树的后根遍历，即可对该二叉链表进行中序遍历即可

<table> 
 <thead> 
  <tr> 
   <th>树</th> 
   <th>森林</th> 
   <th>树、森林用二叉链表的形式存储（孩子兄弟表示法）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>先根遍历</td> 
   <td>先序遍历</td> 
   <td>先序遍历</td> 
  </tr> 
  <tr> 
   <td>后根遍历</td> 
   <td>中序遍历、后序遍历</td> 
   <td>中序遍历</td> 
  </tr> 
 </tbody> 
</table>

# 树的中序遍历问题 #

【二叉树的中序遍历】二叉树遍历的时候都一共有三次经过结点，第二次经过时就是中序遍历（因为度为2，所以有中序遍历）

【树的中序遍历问题】树的度不一定，一般不说中序遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]: /images/20230808/538b0e1e3b984005b236f692b037dba2.png