数据结构中树的三种遍历方式是什么?树是数据结构中一种常用的结构,其遍历方法也是我们学习数据结构所必须要掌握的。今天就和知了姐一起来看看这三种遍历方式吧。
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。二叉树(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学习干货。