二叉树遍历C语言六种算法.pdf

二叉树遍历C语言六种算法

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个

子节点。在二叉树的遍历过程中，我们按照一定的方式访问每个节点。常

用的遍历方式包括前序遍历、中序遍历、后序遍历、层次遍历等。其中，

前序遍历、中序遍历和后序遍历是三种常用的深度优先遍历方法，层次遍

历是广度优先遍历的一种方法。

在C语言中，我们可以使用递归和非递归两种方法来实现二叉树的遍

历。下面将分别介绍这六种遍历算法，并给出相应的代码示例。

1.前序遍历(递归)：

前序遍历先访问根节点，然后递归地遍历左子树和右子树。具体的实

现代码如下：

```c

//前序遍历(递归)

voidpreorderTraversal(TreeNode*root)

if(root==NULL)return;

访问根节点

preorderTraversal(root-left);//递归遍历左子树

preorderTraversal(root-right);//递归遍历右子树

```

2.前序遍历(非递归)：

我们可以使用栈来实现前序遍历的非递归算法。具体的实现代码如下：

```c

//前序遍历(非递归)

voidpreorderTraversal(TreeNode*root)

if(root==NULL)return;

Stack*stack=createStack(;//创建一个栈

push(stack,root);//根节点入栈

while(!isEmpty(stack))

TreeNode*node=pop(stack);//出栈

访问节点

if(node-right!=NULL)push(stack,node-right);//右子节

点入栈

if(node-left!=NULL)push(stack,node-left);//左子节点

入栈

}

destroyStack(stack);//销毁栈

```

3.中序遍历(递归)：

中序遍历先递归地遍历左子树，然后访问根节点，最后递归地遍历右

子树。具体的实现代码如下：

```c

//中序遍历(递归)

voidinorderTraversal(TreeNode*root)

if(root==NULL)return;

inorderTraversal(root-left);//递归遍历左子树

访问根节点

inorderTraversal(root-right);//递归遍历右子树

```

4.中序遍历(非递归)：

使用栈来实现中序遍历的非递归算法。具体的实现代码如下：

```c

//中序遍历(非递归)

voidinorderTraversal(TreeNode*root)

Stack*stack=createStack(;//创建一个栈

TreeNode*current=root;

while(current!=NULL，!isEmpty(stack))

while(current!=NULL)

push(stack,current);//当前节点入栈

current=current-left;//移动到左子节点

}

current=pop(stack);//出栈

访问节点

current=current-right;//移动到右子节点

}

de