二叉树遍历前序中序后序代码

二叉树是一种常见的数据结构，它由一个根节点和两个子节点组成，这些子节点也可以有自己的子节点。根据访问元素的顺序，二叉树遍历可以分为前序遍历、中序遍历和后序遍历。这篇文章将从多个角度来解析三种遍历的代码实现。

前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。下面是前序遍历的伪代码实现：

```

preorder(tree)

if tree == null

return

print(tree.value)

preorder(tree.left)

preorder(tree.right)

```

上述代码是采用了递归的方式来实现二叉树的前序遍历。在遍历左子树和右子树之前，先输出根节点的值。当根节点为空时，函数直接返回。

中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。下面是中序遍历的伪代码实现：

```

inorder(tree)

if tree == null

return

inorder(tree.left)

print(tree.value)

inorder(tree.right)

```

同样地，上述代码也是采用了递归的方式来实现二叉树的中序遍历。与前序遍历不同的是，中序遍历将输出操作放在了左子树与右子树之间。

后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。下面是后序遍历的伪代码实现：

```

postorder(tree)

if tree == null

return

postorder(tree.left)

postorder(tree.right)

print(tree.value)

```

同样地，上述代码也是采用了递归的方式来实现二叉树的后序遍历。在遍历左子树和右子树之后，再输出根节点的值。

递归的实现方式虽然简洁易懂，但是由于需要频繁地进入和退出函数，可能会导致函数栈的溢出。因此，为了提高效率，在实际使用时，可以选择使用迭代的方式来遍历二叉树。

迭代法的实现方式

前序遍历迭代的实现方式是使用栈来存储节点的顺序，代码如下：

```

preorder_iterative(tree)

stack = []

result = []

if tree == null

return result

stack.append(tree)

while stack:

node = stack.pop()

result.append(node.value)

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return result

```

中序遍历迭代的实现方式也是使用栈，代码如下：

```

inorder_iterative(tree)

stack = []

result = []

current = tree

while current or stack:

while current:

stack.append(current)

current = current.left

current = stack.pop()

result.append(current.value)

current = current.right

return result

```

后序遍历的迭代实现方式需要避免重复访问右节点，可以在入栈时加入一个标识符来表示节点是否已经被访问过，代码如下：

```

postorder_iterative(tree)

stack = [(tree, False)]

result = []

while stack:

node, visited = stack.pop()

if node:

if visited:

result.append(node.value)

else:

stack.append((node, True))

stack.append((node.right, False))

stack.append((node.left, False))

return result

```

在以上代码实现中，我们都使用了栈来存储节点的信息，遍历过程中，我们就可以不停地在栈中取出节点。对于栈中存储的信息，我们需要根据不同的遍历方式进行调整。