二叉树的先序,中序,后序遍历程序

二叉树的先序、中序、后序遍历程序

二叉树是数据结构中最重要的基础之一，它的应用非常广泛。而树的遍历是二叉树最基本的操作之一。二叉树的遍历分为三种方式：先序遍历、中序遍历和后序遍历。本文将从多个角度分析二叉树的遍历算法，并给出相应的程序实现。

一、二叉树的定义

在对二叉树的遍历算法进行分析之前，我们需要了解二叉树的定义。

二叉树是一棵有限的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。如果一个节点没有子节点，那么它就是叶子节点。树的顶端节点称作根节点。下面是一个简单的二叉树示例：

```

1

/ \

2 3

/ \

4 5

```

在上面的示例中，根节点是1，它的左子节点是2，右子节点是3。节点2的左子节点是4，右子节点是5。节点3没有子节点。这是一个完整的二叉树。

二、三种遍历方式

1.先序遍历

先序遍历的顺序是“先根节点，然后左子树，最后右子树”。上面的二叉树的先序遍历结果为：1,2,4,5,3。

先序遍历的递归实现代码如下：

```python

def preOrderTraversal(root):

if not root:

return

print(root.val)

preOrderTraversal(root.left)

preOrderTraversal(root.right)

```

2.中序遍历

中序遍历的顺序是“先左子树，然后根节点，最后右子树”。上面的二叉树的中序遍历结果为：4,2,5,1,3。

中序遍历的递归实现代码如下：

```python

def inOrderTraversal(root):

if not root:

return

inOrderTraversal(root.left)

print(root.val)

inOrderTraversal(root.right)

```

3.后序遍历

后序遍历的顺序是“先左子树，然后右子树，最后根节点”。上面的二叉树的后序遍历结果为：4,5,2,3,1。

后序遍历的递归实现代码如下：

```python

def postOrderTraversal(root):

if not root:

return

postOrderTraversal(root.left)

postOrderTraversal(root.right)

print(root.val)

```

三、遍历算法的实现方式

1.递归算法

递归算法是二叉树遍历中最简单的一种算法，也是最容易理解的一种算法。递归遍历二叉树的核心思想就是将一颗大树看作是若干个小树的组合。递归实现的优点是代码简单易懂，缺点是容易栈溢出。在二叉树的遍历中，递归算法的时间复杂度为O(n)，空间复杂度为O(h)。

2.非递归算法

非递归算法是二叉树遍历的另一种重要的方式。它不使用递归，而是使用栈来存储未遍历的节点。非递归算法的优点是避免栈溢出，缺点是代码比较复杂。在二叉树的遍历中，非递归算法的时间复杂度为O(n)，空间复杂度也为O(h)。

四、总结

本文介绍了二叉树的遍历算法，包括先序遍历、中序遍历和后序遍历，并分析了递归算法和非递归算法的优缺点。对于递归算法来说，它的代码非常简洁，而且易于理解；对于非递归算法来说，它避免了栈溢出问题，而且有些时候执行效率还会更优。因此，在实际编程中，选择哪种算法主要取决于具体的应用场景。