二叉树的建立与遍历(c语言实现)
时间: 2023-08-05 19:13:27 浏览: 36
二叉树是一种重要的数据结构,它由节点和指向子节点的指针组成。二叉树的节点最多有两个子节点,左子节点和右子节点。在下面的代码中,我们将使用C语言实现二叉树的建立和遍历。
首先,我们定义二叉树节点的结构体:
```c
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
```
其中,`data`表示节点存储的数据,`left`和`right`分别指向左子节点和右子节点。
接下来,我们实现二叉树的建立函数。我们可以使用递归的方式来创建二叉树,先创建根节点,然后递归创建左子树和右子树。当遇到空节点时返回NULL。
```c
Node* createTree() {
int data;
scanf("%d", &data);
if (data == -1) { // 遇到空节点
return NULL;
}
Node* root = (Node*)malloc(sizeof(Node));
root->data = data;
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root;
}
```
在上面的代码中,我们使用`scanf()`函数读取输入数据,并且当输入-1时表示遇到空节点,返回NULL。否则,我们创建一个新节点,并递归创建左子树和右子树。
接下来,我们可以实现二叉树的前序遍历、中序遍历和后序遍历。这里我们使用递归的方式进行遍历。
```c
// 前序遍历
void preOrder(Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 输出当前节点
preOrder(root->left); // 遍历左子树
preOrder(root->right); // 遍历右子树
}
// 中序遍历
void inOrder(Node* root) {
if (root == NULL) {
return;
}
inOrder(root->left); // 遍历左子树
printf("%d ", root->data); // 输出当前节点
inOrder(root->right); // 遍历右子树
}
// 后序遍历
void postOrder(Node* root) {
if (root == NULL) {
return;
}
postOrder(root->left); // 遍历左子树
postOrder(root->right); // 遍历右子树
printf("%d ", root->data); // 输出当前节点
}
```
在上面的代码中,我们先判断当前节点是否为空,如果不为空,则按照前序遍历、中序遍历和后序遍历的顺序遍历左子树和右子树,并输出当前节点。
最后,我们可以在`main()`函数中调用上述函数来测试二叉树的建立和遍历。
```c
int main() {
Node* root = createTree();
printf("前序遍历:");
preOrder(root);
printf("\n中序遍历:");
inOrder(root);
printf("\n后序遍历:");
postOrder(root);
return 0;
}
```
这样,我们就完成了二叉树的建立和遍历。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)