c语言二叉树的创建与遍历
时间: 2023-10-04 18:09:49 浏览: 51
二叉树是一种非常重要的数据结构,它在计算机科学中得到广泛应用。下面是C语言中创建和遍历二叉树的示例代码。
## 创建二叉树
对于二叉树的创建,我们可以采用递归的方式,先创建左子树,再创建右子树,最后将左右子树链接到根节点上。下面是一段示例代码。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data; // 存储数据
struct node* left; // 左子树指针
struct node* right; // 右子树指针
} Node;
// 创建二叉树
Node* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL; // 如果输入-1,表示该节点不存在
}
Node* root = (Node*)malloc(sizeof(Node));
root->data = val;
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root;
}
```
## 遍历二叉树
遍历二叉树有三种方式:前序遍历、中序遍历和后序遍历。下面分别给出它们的示例代码。
### 前序遍历
前序遍历的顺序是先访问根节点,再访问左子树,最后访问右子树。下面是一段示例代码。
```c
void preOrder(Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 访问根节点
preOrder(root->left); // 遍历左子树
preOrder(root->right); // 遍历右子树
}
```
### 中序遍历
中序遍历的顺序是先访问左子树,再访问根节点,最后访问右子树。下面是一段示例代码。
```c
void inOrder(Node* root) {
if (root == NULL) {
return;
}
inOrder(root->left); // 遍历左子树
printf("%d ", root->data); // 访问根节点
inOrder(root->right); // 遍历右子树
}
```
### 后序遍历
后序遍历的顺序是先访问左子树,再访问右子树,最后访问根节点。下面是一段示例代码。
```c
void postOrder(Node* root) {
if (root == NULL) {
return;
}
postOrder(root->left); // 遍历左子树
postOrder(root->right); // 遍历右子树
printf("%d ", root->data); // 访问根节点
}
```
使用示例:
```c
int main() {
Node* root = createTree();
printf("前序遍历结果:");
preOrder(root);
printf("\n");
printf("中序遍历结果:");
inOrder(root);
printf("\n");
printf("后序遍历结果:");
postOrder(root);
printf("\n");
return 0;
}
```
注意:在实际编写代码时,需要考虑内存泄漏的问题,需要释放创建的节点内存。