C语言二叉树的先序,中序,后序遍历

二叉树是一种树形结构，它的每个节点至多拥有两个子节点。二叉树通过遍历来访问每个节点。常见的遍历方式包括先序遍历、中序遍历和后序遍历。在C语言中，我们可以使用指针来实现二叉树的创建和遍历。本文将从多个角度介绍C语言二叉树的先序、中序、后序遍历。

一、关于二叉树的定义

在二叉树中，每个节点最多只能有两个子节点。如果一个节点没有子节点，那么它就是叶子节点。如下图所示，一个二叉树由根节点、左子树和右子树组成。


二、指针实现二叉树的创建

在C语言中，我们可以使用结构体和指针来方便地实现二叉树的创建和遍历。二叉树的每个节点包括数据和指向左右子节点的指针。首先，我们需要定义二叉树节点的结构体。

```

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

};

```

接下来，我们可以通过递归的方式创建二叉树。具体而言，首先创建根节点，然后递归创建左子树和右子树。递归创建左子树和右子树的过程类似于创建根节点。最后返回根节点的指针。

```

struct TreeNode* createTree() {

struct TreeNode *root;

int data;

scanf("%d", &data);

if(data == -1) {

root = NULL;

} else {

root = (struct TreeNode*)malloc(sizeof(struct TreeNode));

root -> val = data;

root -> left = createTree();

root -> right = createTree();

}

return root;

}

```

三、先序遍历

先序遍历的顺序是“根、左、右”。即遍历根节点，然后遍历左子树，最后遍历右子树。先序遍历的实现非常简单，只需要按照遍历顺序打印节点的值即可。代码如下：

```

void preOrderTraversal(struct TreeNode *root) {

if(root) {

printf("%d ", root -> val); // 遍历根节点

preOrderTraversal(root -> left); // 遍历左子树

preOrderTraversal(root -> right); // 遍历右子树

}

}

```

四、中序遍历

中序遍历的顺序是“左、根、右”。即先遍历左子树，然后遍历根节点，最后遍历右子树。中序遍历可以用来实现二叉搜索树的排序功能，因为二叉搜索树的中序遍历的结果是有序的。中序遍历的实现也非常简单，只需要按照遍历顺序打印节点的值即可。代码如下：

```

void inOrderTraversal(struct TreeNode *root) {

if(root) {

inOrderTraversal(root -> left); // 遍历左子树

printf("%d ", root -> val); // 遍历根节点

inOrderTraversal(root -> right); // 遍历右子树

}

}

```

五、后序遍历

后序遍历的顺序是“左、右、根”。即先遍历左子树，然后遍历右子树，最后遍历根节点。后序遍历可以用来实现二叉树的后缀表达式计算、内存回收等功能。后序遍历的实现也非常简单，只需要按照遍历顺序打印节点的值即可。代码如下：

```

void postOrderTraversal(struct TreeNode *root) {

if(root) {

postOrderTraversal(root -> left); // 遍历左子树

postOrderTraversal(root -> right); // 遍历右子树

printf("%d ", root -> val); // 遍历根节点

}

}

```