数据结构中树的三种遍历方式是什么？数据结构基础干货速码

知了堂姐

2024-07-09 11:12:24

0次

数据结构中树的三种遍历方式是什么？树是数据结构中一种常用的结构，其遍历方法也是我们学习数据结构所必须要掌握的。今天就和知了姐一起来看看这三种遍历方式吧。

树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。二叉树（Binary Tree）是特殊的树形结构，特点是每个结点至多只有两棵子树，而且子树存在左右之分。

一棵树的三种遍历方式包括先序遍历，中序遍历，后序遍历。以下图种的树为例：

1、先序遍历：

（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

Tips：
①先访问根结点A，

②左子树（B）先序遍历，得到B-D-E，右子树（C）先序遍历，得到C-F-H

③再对B的右子树（E）先序遍历，得到 E-G-I

④合并全部得到 A-B-D-E-G-I-C-F-H

2、中序遍历：

（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。

Tips：
①先中序遍历左子树（B），得到D-B-E，E存在子树，中序遍历（E），得到G-E-I，因此得到D-B-G-E-I

②访问根结点得到 A，总的为D-B-G-E-I-A

③中序遍历右子树（C）得到F-C-H

④合并全部得到D-B-G-E-I-A-F-C-H

3、后序遍历：

（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

Tips：
①先后序遍历左子树（B），得到D-E-B，E存在子树，后序遍历（E），得到G-I-E，因此得到D-G-I-E-B

②后序遍历右子树（C）得到F-H-C

③访问根结点A

④合并全部得到D-G-I-E-B-F-H-C-A

以上就是数据结构中树的三种常用遍历方式，其实除了以上三种，还有一种叫做层次遍历，从根结点开始访问；逐层进行访问，在同一层中，按从左到右的方式进行访问。以上图为例最终遍历结果为A-B-C-D-E-F-H-G-I。关注成都知了堂Java培训机构，带你了解更多Java学习干货。

上一篇：线性表和链表的区别与联系是什么？线性表包括链表吗

下一篇：数据结构的三种基本类型包括哪三种？最常用的是什么