小竞 (编辑)
树是一种几乎普遍存在的数据结构，因此在大多数编程语言中都可以找到。具体的实现可能不同，但许多基本操作仍然相同。当你使用树时，通常需要访问树中的元素。这个过程称为遍历，通常按照特定的顺序进行。其中一个示例是前序遍历，本文将重点介绍它的工作原理、如何实现以及最佳实践和实际应用。
什么是前序遍历，为什么它很重要？
当我们有一棵二叉树时，我们有一个根节点和两个分支。这些分支有自己的节点，它们又分支出更多的节点，直到结构完成。有许多访问这些节点的方法。主要的三种方法是：
- 中序遍历 – 这是我们递归地访问左子树，访问根节点，然后探索右子树的过程。中序遍历按升序工作，因此通常用于创建排序列表。
- 后序遍历 – 这个过程首先访问左子树和右子树，然后到达节点。通常用于删除树。
- 前序遍历 – 本文的重点是前序遍历，它涉及从根节点开始，然后依次访问左子树和右子树。
前序遍历很重要，因为它在计算机科学中有许多应用。它不仅用于首次创建树，还用于对树执行操作。这是因为它按特定顺序访问节点，以保留树的属性。因此，前序遍历通常在深度优先搜索(dfs)算法中使用，其中我们希望沿着每个分支深入探索结构。
前序遍历的实现
有两种主要的使用前序遍历的方法 – 递归和使用堆栈结构。让我们依次探讨这两种方法。
递归方法
递归前序遍历的一般语法可以描述如下：
preordertraversal(node):
if node is null:
return
process(node)
preordertraversal(node.left)
preordertraversal(node.right)首先，我们检查节点是否为空。如果是空的，就没有更多的节点可查看了。否则，我们对节点执行我们想要的操作，然后按照左子树和右子树的顺序递归调用该函数。让我们看一个python的例子：
class treenode:
def __init__(self, value):
self.value = value
self.left = none
self.right = none
def preordertraversal(node):
if node is none:
return
print(node.value)
preordertraversal(node.left)
preordertraversal(node.right)
root = treenode(1)
root.left = treenode(2)
root.right = treenode(3)
root.left.left = treenode(4)
root.left.right = treenode(5)
root.right.left = treenode(6)
root.right.right = treenode(7)
preordertraversal(root)我们首先声明了”treenode”类，其中包含了”__init__”构造方法，该方法以”self”和”value”为参数。类实例化时使用”value”参数进行初始化，”self”引用当前实例。
然后，将“value”参数赋值给当前实例的属性，并将“left”和“right”属性都初始化为“none”。
之后，定义了一个名为“preordertraversal（node）”的函数，用于执行遍历。当前节点由“node”表示。如果节点等于none，则不需要进行进一步操作。然后打印当前节点的值。
然后递归地在左节点和右节点上调用主函数。最后，我们创建了一个二叉树，根节点为1，第一个左右子节点为2和3，第二个左右子节点为4和5，依此类推。从树的根节点开始调用主函数，并打印结果。这些可以在下面的图片中看到。
前序遍历使用递归方法实现。
©jingzhengli.com
迭代方法
进行前序遍历的另一种方法是迭代地使用堆栈结构在访问节点之前存储它们。考虑以下代码块：
class treenode:
def __init__(self, value):
self.value = value
self.left = none
self.right = none
def iterativepreordertraversal(root):
if root is none:
return
stack = []
stack.append(root)
while stack:
node = stack.pop()
print(node.value)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
root = treenode(1)
root.left = treenode(2)
root.right = treenode(3)
root.left.left = treenode(4)
root.left.right = treenode(5)
root.right.left = treenode(6)
root.right.right = treenode(7)
iterativepreordertraversal(root)我们创建与之前相同的类，具有相同的构造方法，将左节点和右节点初始化为“none”。然后定义主迭代方法“iterativepreordertraversal（root）”，它以根节点作为输入。
之后，我们创建一个堆栈，并将根节点添加到其中。然后使用一个while循环执行程序的主要操作。只要堆栈中有节点，就会继续进行。当删除一个节点时，将其值打印到控制台。右节点首先添加，因为堆栈遵循先进后出（lifo）原则。因此，如果我们想要先处理左节点，则它们必须最后添加。
创建了一个类似的二叉树，调用了主函数，并打印了节点。输出在下面的图片中。
前序遍历采用迭代方法，使用堆栈结构存储节点。
©jingzhengli.com
前序遍历的复杂度
幸运的是，在二叉树中，前序遍历的时间复杂度通常等于o（n），其中n是节点的数量。换句话说，复杂性取决于树中的节点数量。这是因为无论使用哪种方法，我们都必须访问每个节点一次。在最好的情况下，仅有一个节点，这将需要常数时间，即o（1）。但是，这种情况非常罕见，所以在大多数情况下，复杂度为o（n）。当树基本上是线性的时候，即形成一个链表时，我们可能会有最坏情况复杂度为o（n2）。再次强调，这是使用前序遍历的罕见情况。
空间复杂度通常等于o(h)，其中h是树的高度。然而，在平衡树的情况下，这可以变为o(log n)，因为高度与节点数目的对数成比例。这是当高度远小于总节点数时的情况。对于最坏情况下的不平衡树，复杂度接近o(n)，因为它依赖于节点数目。
前序遍历的优点、缺点和应用
与任何方法一样，前序遍历也有其优点和缺点。这些在下表中描述。
| 优点 | 缺点 |
|---|---|
| 访问树时一种直观的方式，首先访问根节点 | 当我们需要首先访问子节点时不适用 |
| 易于重现精确的树结构 | 在递归实现时可能具有较高的空间复杂度 |
| 实现上灵活 | 访问顺序不灵活 |
正如你所见，前序遍历有许多好处，但它可能会占用较多的内存，并且在执行过程中相当严格。因为它以一种自然的方式访问节点，我们可以相对容易地使用它来从一组值中重构原始的树结构。同样，我们可以使用它来分解一棵树，以后会重新构建。前序遍历还有助于转换表达式，例如从中缀转换为前缀或后缀。最后，深度优先搜索算法使用前序遍历，其中每个节点都按顺序访问以解决问题。
总结
当我们想要以特定且直观的顺序遍历树时，前序遍历是一种非常有用的技术。尽管它的设计并不灵活，但可以根据需要使用递归或迭代来执行。它的主要用途是重构或分解树，以及在深度优先搜索算法中使用。由于它代表了我们处理树结构的自然方式，了解前序遍历的工作原理无疑会在编程之旅中帮助你。
