二叉树遍历顺序

二叉树是一种常见的数据结构，在很多领域都有应用。二叉树中的结点最多只能有两个子节点，分别称为左子节点和右子节点。在实际应用场景中，我们经常需要遍历二叉树，访问每个结点的值，以实现对其进行操作。

二叉树遍历指的是按照一定的顺序访问二叉树中的所有结点，常见的遍历方式有前序遍历、中序遍历和后序遍历。正如其名，前序遍历是先访问结点自身，再访问其左子树和右子树；中序遍历则是先访问左子树，再访问结点自身，最后访问右子树；后序遍历则是先访问左子树，再访问右子树，最后访问结点自身。

在不同的场景下，采用不同的遍历方式也会得到不同的效果。比如在计算表达式的值时，采用前序遍历能够得到前缀表达式；采用后序遍历能够得到后缀表达式；而中序遍历则可以将表达式转换为中缀表达式。

在二叉树的实现中，通常采用递归的方式来进行遍历。以前序遍历为例，代码实现如下：

```python

def preorder_traversal(root):

if not root:

return

print(root.val)

preorder_traversal(root.left)

preorder_traversal(root.right)

```

在这段代码中，我们首先判断当前的根节点是否为空，如果为空则直接返回；否则先输出根节点的值，再递归调用左子树和右子树的前序遍历函数。

除了递归方式之外，还有一种非递归的方式进行遍历，即采用栈来实现。以前序遍历为例，代码实现如下：

```python

def preorder_traversal(root):

if not root:

return []

stack = [root]

res = []

while stack:

node = stack.pop()

res.append(node.val)

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return res

```

在这段代码中，我们先将根节点入栈，然后不断地弹出栈顶元素，访问其值，并将其右子节点和左子节点入栈，保证左子节点先于右子节点被访问。

除了前序遍历、中序遍历和后序遍历之外，还有一种比较特殊的遍历方式，即层序遍历。层序遍历是按照二叉树的层次，从上到下、从左到右地访问每个结点。在实际应用中，层序遍历常常用于查找最短路径等场景。

```python

def level_order_traversal(root):

if not root:

return []

queue = [root]

res = []

while queue:

level = []

for _ in range(len(queue)):

node = queue.pop(0)

level.append(node.val)

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

res.append(level)

return res

```

在这段代码中，我们使用队列来实现层序遍历。首先将根节点入队，然后按照层次依次将每个节点出队，访问其值，并将其左右子节点入队。最后将每一层的结果按照顺序存储在一个列表中，并将其返回。

总之，二叉树遍历顺序是二叉树操作中的重要环节，不同的遍历方式对于不同的场景有不同的作用。无论是递归还是非递归方式，掌握二叉树遍历方法对于编写高效的算法和提高编程技能都非常重要。