二叉树三种遍历代码

二叉树是一种重要的数据结构，它有许多应用。遍历是二叉树的一种基本操作，常用的遍历方法有三种：前序遍历、中序遍历和后序遍历。在本文中，我们将探讨这三种遍历方法的实现代码并进行分析。

前序遍历代码

前序遍历的顺序是：根节点→左子树→右子树。前序遍历的代码实现如下：

``` python

def preorderTraversal(root):

if root:

print(root.val)

preorderTraversal(root.left)

preorderTraversal(root.right)

```

这是最简单的递归实现方式，它首先输出根结点，然后递归遍历左子树，最后递归遍历右子树。由于递归的特性，代码非常简洁。

中序遍历代码

中序遍历的顺序是：左子树→根节点→右子树。中序遍历的代码实现如下：

``` python

def inorderTraversal(root):

if root:

inorderTraversal(root.left)

print(root.val)

inorderTraversal(root.right)

```

同样，这也是递归实现方式。它首先递归遍历左子树，然后输出根结点，最后递归遍历右子树。与前序遍历代码相比，它只是改变了输出的顺序。

后序遍历代码

后序遍历的顺序是：左子树→右子树→根节点。后序遍历的代码实现如下：

``` python

def postorderTraversal(root):

if root:

postorderTraversal(root.left)

postorderTraversal(root.right)

print(root.val)

```

同样地，这也是递归实现方式。它首先递归遍历左子树，然后递归遍历右子树，最后输出根结点。

分析

前序、中序和后序遍历方法之间的区别在于它们输出节点的顺序。但是它们所遍历的整个树结构是完全相同的。这就意味着，使用同样的数据结构，我们可以通过不同的遍历方式来实现不同的算法。

对于递归实现方式，我们可以通过堆栈来实现非递归版本的遍历代码。非递归的前序遍历、中序遍历和后序遍历方法都可以使用堆栈来实现。通过遍历树的每个节点，将节点的左子树和右子树压入堆栈中，然后处理栈顶元素，最后弹出该元素。

另外，我们还可以使用Morris遍历方法来实现前序遍历、中序遍历和后序遍历。该方法不使用堆栈，可以将遍历的空间复杂度降至常数级别。具体来说，该方法基于线索二叉树的思想，使每个节点的右子树指向当前节点的后继节点。这种方法易于实现，但仅适用于普通的二叉树，不适用于带有重复节点的二叉树。