二叉树前序、中序遍历的递归算法

2024年2月7日发(作者：)

二叉树前序、中序遍历的递归算法

二叉树的前序遍历和中序遍历是二叉树遍历的两种常见方式。在讲解这两种遍历算法之前，我们先来了解下二叉树的概念。

二叉树是一种常见的树型结构，它由若干个节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。一个二叉树的节点可以为空，即没有子节点，此时我们称为空节点。

在二叉树中，每个节点包含一个值和两个指向子节点的指针，分别指向左子节点和右子节点。每个节点的顺序遍历方式有三种，分别是前序遍历、中序遍历和后序遍历。

前序遍历的顺序是先访问根节点，再访问左子节点，最后访问右子节点。中序遍历的顺序是先访问左子节点，再访问根节点，最后访问右子节点。

现在我们就来分别讲解一下二叉树的前序遍历和中序遍历的递归算法。

首先是前序遍历算法。前序遍历算法的递归实现很简单，可以按照以下步骤进行：

1.如果当前节点为空，直接返回。

2.访问当前节点的值。

3.对当前节点的左子节点进行前序遍历。

4.对当前节点的右子节点进行前序遍历。

下面是前序遍历算法的完整代码实现：

```python

def preorder_traversal(root):

if root is None:

return

print()

preorder_traversal()

preorder_traversal()

```

其中，`root`表示当前节点，``表示该节点的值。``表示左子节点，``表示右子节点。

接下来是中序遍历算法。中序遍历算法的递归实现也很简单，可以按照以下步骤进行：

1.如果当前节点为空，直接返回。

2.对当前节点的左子节点进行中序遍历。

3.访问当前节点的值。

4.对当前节点的右子节点进行中序遍历。

下面是中序遍历算法的完整代码实现：

```python

def inorder_traversal(root):

if root is None:

return

inorder_traversal()

print()

inorder_traversal()

```

同样，`root`表示当前节点，``表示该节点的值。``表示左子节点，``表示右子节点。

通过递归调用，前序遍历算法和中序遍历算法可以遍历二叉树的所有节点，并按照规定的顺序输出节点的值。

总结来说，二叉树的前序遍历和中序遍历都是递归算法。前序遍历的顺序是根节点、左子节点、右子节点；中序遍历的顺序是左子节点、根节点、右子节点。在实际应用中，我们可以根据需要选择使用前序遍历或中序遍历来对二叉树进行遍历和操作。