树遍历的时间复杂度是多少?

1.概述

在计算机科学中,线性数据结构只能以一种逻辑方式遍历。但是，可以用几种不同的方式遍历树形数据结构。

在本教程中，我们将讨论遍历树的各种方法以及这种操作的时间复杂度。

2.什么是树遍历?

树遍历是只访问树中的每个节点一次的过程。从一个当前节点开始，我们可以到达的节点可能不止一个。因此，可以有几个访问节点的不同顺序。让我们举个例子:

可以以多种不同的方式遍历此树的节点。一些遍历顺序是:

• 订单1:
• 订单2:
• 订单3:

因此，根据被访问的节点，遍历分为两类:深度优先遍历和层次顺序或广度优先遍历。

深度优先遍历可以进一步分为三种遍历类型:按次序的,预购,后序遍历。

3.树遍历技术

根据顺序遍历，我们首先访问左子树中的节点，然后是根节点和右子树中的节点。我们先搜索左边叶子节点开始有序遍历的左子树。

在预购遍历,我们首先访问根节点，然后是左子树，最后是右子树。

在后序遍历的情况下，我们先访问左子树，然后是右子树，最后是根节点。

最后，对于层次顺序或宽度优先遍历，我们访问树中的所有节点水平时尚的水平。我们从根节点开始，然后进入下一层访问节点。

4.例子

现在我们以树为例，让我们找出树的各种遍历:

如果我们在这个例子树中应用有序遍历，这棵树的有序遍历是

在预顺序遍历的情况下，我们首先访问根节点。因此，这棵树的预顺序遍历将是:

在后序遍历中，我们最后遍历根节点。因此，该树的后序遍历将为:

示例树的层次顺序遍历如下:

5.树遍历的时间复杂度

一般情况下，所有遍历算法都只访问树中的每个节点一次。因此，所有遍历算法的时间复杂度为当一棵树包含节点。

为了验证总的时间复杂度，我们用一个极端情况，我们要找出访问所有节点的时间复杂度。如果一棵树有节点，那么时间复杂度树的可定义为:

是树的左边的节点数，和表示常数时间。现在我们假设给定的树是a右偏态树。对于右倾斜的树，树的左边将是空的。所以:

如果我们继续，我们将得到:

表示遍历一棵空树，需要常数时间:

因此，我们验证了所有的树遍历算法取时间。

6.结论

在本教程中，我们学会了几种遍历树的方法。我们呈现每个遍历的算法，并用示例演示。最后，我们分析了遍历算法的时间复杂性。