1.概述
在计算机科学中,线性数据结构只能以一种逻辑方式遍历。但是,可以用几种不同的方式遍历树形数据结构。
在本教程中,我们将讨论遍历树的各种方法以及这种操作的时间复杂度。
2.什么是树遍历?
树遍历是只访问树中的每个节点一次的过程。从一个当前节点开始,我们可以到达的节点可能不止一个。因此,可以有几个访问节点的不同顺序。让我们举个例子:

可以以多种不同的方式遍历此树的节点。一些遍历顺序是:
- 订单1:
- 订单2:
- 订单3:
因此,根据被访问的节点,遍历分为两类:深度优先遍历和层次顺序或广度优先遍历。
深度优先遍历可以进一步分为三种遍历类型:按次序的,预购,后序遍历。
3.树遍历技术
根据顺序遍历,我们首先访问左子树中的节点,然后是根节点和右子树中的节点。我们先搜索左边叶子节点开始有序遍历的左子树。
在预购遍历,我们首先访问根节点,然后是左子树,最后是右子树。
在后序遍历的情况下,我们先访问左子树,然后是右子树,最后是根节点。
最后,对于层次顺序或宽度优先遍历,我们访问树中的所有节点水平时尚的水平。我们从根节点开始,然后进入下一层访问节点。
4.例子
现在我们以树为例,让我们找出树的各种遍历:

如果我们在这个例子树中应用有序遍历,这棵树的有序遍历是
在预顺序遍历的情况下,我们首先访问根节点。因此,这棵树的预顺序遍历将是:
在后序遍历中,我们最后遍历根节点。因此,该树的后序遍历将为:
示例树的层次顺序遍历如下:
5.树遍历的时间复杂度
一般情况下,所有遍历算法都只访问树中的每个节点一次。因此,所有遍历算法的时间复杂度为当一棵树包含
节点。
为了验证总的时间复杂度,我们用一个极端情况,我们要找出访问所有节点的时间复杂度。如果一棵树有节点,那么时间复杂度
树的可定义为:
是树的左边的节点数,和
表示常数时间。现在我们假设给定的树是a右偏态树。对于右倾斜的树,树的左边将是空的。所以
:
如果我们继续,我们将得到:
表示遍历一棵空树,需要常数时间:
因此,我们验证了所有的树遍历算法取时间。
6.结论
在本教程中,我们学会了几种遍历树的方法。我们呈现每个遍历的算法,并用示例演示。最后,我们分析了遍历算法的时间复杂性。