用C++语言编写具体函数实现二叉树的创建,前序、中序、后序遍历等基本操作,并在主函数中输出
时间: 2023-06-08 09:08:18 浏览: 91
二叉树的先序、中序、后序、分层遍历C++实现
4星 · 用户满意度95%
好的,我可以回答您的问题,以下是在C语言中实现二叉树的创建、前序、中序、后序遍历以及主函数中的代码:
```c
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* left;
struct node* right;
};
// 创建一个节点,返回该节点的地址
struct node* create_node(int data){
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// 往二叉树中插入一个节点
struct node* insert_node(struct node* root, int data){
if(root == NULL){ // 如果二叉树为空
root = create_node(data);
}else if(data <= root->data){ // 如果需要插入的值比根节点小或相等
root->left = insert_node(root->left, data); // 在左子树中插入该节点
}else{ // 如果需要插入的值比根节点大
root->right = insert_node(root->right, data); // 在右子树中插入该节点
}
return root;
}
// 前序遍历二叉树(根节点-左子树-右子树)
void pre_order_traversal(struct node* root){
if(root == NULL){ // 递归出口:如果二叉树为空
return;
}
printf("%d ", root->data); // 先输出根节点
pre_order_traversal(root->left); // 递归遍历左子树
pre_order_traversal(root->right); // 递归遍历右子树
}
// 中序遍历二叉树(左子树-根节点-右子树)
void in_order_traversal(struct node* root){
if(root == NULL){ // 递归出口:如果二叉树为空
return;
}
in_order_traversal(root->left); // 递归遍历左子树
printf("%d ", root->data); // 输出根节点
in_order_traversal(root->right); // 递归遍历右子树
}
// 后序遍历二叉树(左子树-右子树-根节点)
void post_order_traversal(struct node* root){
if(root == NULL){ // 递归出口:如果二叉树为空
return;
}
post_order_traversal(root->left); // 递归遍历左子树
post_order_traversal(root->right); // 递归遍历右子树
printf("%d ", root->data); // 输出根节点
}
int main(){
// 创建二叉树
struct node* root = NULL;
root = insert_node(root, 8);
root = insert_node(root, 3);
root = insert_node(root, 10);
root = insert_node(root, 1);
root = insert_node(root, 6);
root = insert_node(root, 14);
root = insert_node(root, 4);
root = insert_node(root, 7);
root = insert_node(root, 13);
// 前序遍历二叉树
printf("前序遍历结果:");
pre_order_traversal(root);
printf("\n");
// 中序遍历二叉树
printf("中序遍历结果:");
in_order_traversal(root);
printf("\n");
// 后序遍历二叉树
printf("后序遍历结果:");
post_order_traversal(root);
printf("\n");
return 0;
}
```
上述程序便可以实现二叉树的创建、前序、中序、后序遍历等基本操作,运行程序可以得到输出结果:
```
前序遍历结果:8 3 1 6 4 7 10 14 13
中序遍历结果:1 3 4 6 7 8 10 13 14
后序遍历结果:1 4 7 6 3 13 14 10 8
```
阅读全文