树的遍历

以你之姓@ 2023-01-18 06:48 45阅读 0赞

**首先声明一下，本章节只将理论，后期有空会补充相应代码。**

**我们知道树的遍历有先序遍历，中序遍历，后序遍历。但是给了我们一棵树，如何根据指定的比遍历方式，得出最终的结果呢，这就是答主接下来要说内容。**

ps：时间原因，直接在纸上画了…

**首先给出原图：**  
![这是图片][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MjUxNTQ3_size_16_color_FFFFFF_t_70]

### 1.先序遍历 ###

这个比较简单，大家一般都能写对。我们知道先序遍历的特点是**根左右**  
则我们：

1、先从结点A出发，判断A是否是根，是，则记录A。

2.下面我们要进行“左”，我们走到了B，**这个时候，我们要B看成一颗树，首先我们判断B是否是根结点，是，则记录B**

3.接下来我们继续进行**左**操作，这个时候我们发现**树B左孩子**为空，那么我们需要进行**右**操作。

4.这个时候我们来到C，**则我们以C**为根，把**C**以及其子孩子看成一棵树，让后继续遍历  
……  
……  
……  
**依次这样遍历下去，我们得出最后结果为 ABCDEFGH**

### 2. 中序遍历 ###

**前言：首先要知道中序遍历的顺序是 左 根 右**

步骤：  
1.我们首先从A出发，看看A是否右**左孩子**，这时候我们发现有左孩子**B**,则我们来到了左孩子这里。

2.以**B**出发，将B以及其子孩子看成一棵树，这个时候我们判断B是否有左孩子，发现B **没有左孩子**，那么按照**中序遍历的规则——左根右**，可以知道，没有左孩子了，那我们直接输出根节点B

3.现在我们来到了**C**,这个时候我们以**C**为根节点看成一颗树，这个时候，我们发现C有**左孩子**，那么我们去遍历它的左孩子。

4.现在我们来到了D，发现D没有左孩子，也就是左边已经遍历了，但是没有发现结点，则我们输出根节点**D**

5.**这个时候以C为根结点的树的左孩子已经遍历完，我们可以输出根节点C，接着是它的右孩子E**

6.**那么，这时以A为根节点的树的左孩子我们已经遍历完，我们可以输出根节点A了**  
……  
……  
……  
**这样遍历下去。我们得到的结果为：BDCEAFHG**

### 3.后序遍历 ###

\*\*前言：我们知道后序遍历的顺序是 左 右 根 \*\*

1.**我们首先从A出发,判断一下它是否有左孩子，发现有左孩子B，则来到B**

2.**以B为出发点看作一棵树，则我们发现B不含有左子树，按照后序遍历规则，我们看到B含有右子  
树，则我们来到右子树C**

3.**我们以C为出发点，看成一颗树，判断C是否有左孩子，发现有，则我们来到了D**

4.**我们以D为出发点，看成一棵树，判断D是否有左孩子，发现D没有左孩子，再判断D是否有右孩子，发现也没有右孩子，那么我们按照 左右根 的顺序 ，可以输出根结点D**

5.**现在我们我们回到根节点C，发现C也含有右孩子，那么我们来到它的右孩子E**

6.**我们来到了E，发现E没有左右孩子，那么我们可以输出根节点E**

7.**这个时候以C为根节点的树的左右孩子已经遍历完，我们可以输出根节点C**

8.**以B为根节点树的左右孩子也已经遍历完，可以输出根节点B**

9.**以A根结点的树的左孩子已经遍历完，我们按照后序遍历顺序，来到以A为根结点的右孩子F以及按照以上规则遍历。**

……  
……  
……  
10.**最后，我们得出结果为 DECBHGFA**

就讲到这里了，如果有错误或者需要改进的地方，请大家及时指出。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MjUxNTQ3_size_16_color_FFFFFF_t_70]: /images/20221021/943596dcc7d24f3e9de1b0e878583bc6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读

相关树的层次遍历

层次遍历简介 > 广度优先在面试里出现的频率非常高，整体属于简单题。而广度优先遍历又叫做层次遍历，基本过程如下： ![image.png][] > 层次遍历就是从根节

￡神魔★判官ぃ/ 2024年03月23日 18:33/ 0 赞/ 41 阅读

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

文章目录 \[总结\] 二叉树、树、森林三者遍历比较树的中序遍历问题 \[总结\] 二叉树、树、森林三者遍历比较【三种遍历方法对比】 <tabl

叁歲伎倆/ 2023年08月17日 17:43/ 0 赞/ 124 阅读

相关树的遍历汇总

[算法笔记总目录][Link 1] 二叉树遍历先序遍历 //先序遍历的实现 void preorder(node root){ if

客官°小女子只卖身不卖艺/ 2023年02月23日 08:12/ 0 赞/ 1 阅读

相关树的遍历

首先声明一下，本章节只将理论，后期有空会补充相应代码。我们知道树的遍历有先序遍历，中序遍历，后序遍历。但是给了我们一棵树，如何根据指定的比遍历方式，得出最终的结果呢，这就是

以你之姓@/ 2023年01月18日 06:48/ 0 赞/ 46 阅读

相关二叉树的遍历——先序遍历、中序遍历、后序遍历

遍历二叉树（本文的二叉树均使用指针方式构建）先序遍历操作定义：若二叉树为空，则空操作；否则： 1. 访问根节点； 2. 先序遍历左子树； 3

淡淡的烟草味﹌/ 2022年12月01日 15:44/ 0 赞/ 248 阅读

相关二叉树的遍历（前序遍历、中序遍历、后序遍历）

二叉树在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作左子树和右子树。树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结

短命女/ 2022年07月15日 16:07/ 0 赞/ 340 阅读

相关遍历节点树、遍历元素树、遍历API、查找 API

遍历节点数 > 深度优先算法，递归调用 -------------------- 节点树 > 包含所有节点对象的树 > arguments.callee:指

墨蓝/ 2022年07月14日 04:00/ 0 赞/ 239 阅读

相关树的遍历-深度优先遍历和广度优先遍历

深度优先遍历类似于树的先序遍历。假设给定初态是图中所有顶点均未被访问过，从图中某一顶点vi出发遍历图中的定义如下：首先访问出发点vi，并将其访问标志置为1；然后，从vi出发点依

电玩女神/ 2022年05月27日 07:20/ 0 赞/ 552 阅读

相关遍历树

遍历树结构数据 ![1485349-20190531095025028-1648193253.png][] watch: {

青旅半醒/ 2021年12月18日 16:45/ 0 赞/ 257 阅读

相关一般树的遍历和图的遍历的比较

最近在做有关树的题目的时候，很多时候都会遇到要遍历树。这里就不再说关于二叉树的遍历了。具体可以参考一下另一篇博客[二叉树][Link 1]。这里谈一下一般的树的遍历——也就是说

清疚/ 2021年09月21日 07:02/ 0 赞/ 338 阅读