二叉树基本操作c语言实现
时间: 2023-08-02 14:26:04 浏览: 57
以下是二叉树基本操作的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
//创建二叉树节点
TreeNode* createNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
//创建二叉树
TreeNode* createTree() {
int data;
scanf("%d", &data);
if (data == -1) { //输入-1表示该节点为空
return NULL;
}
TreeNode* root = createNode(data);
printf("请输入%d的左子节点:", data);
root->left = createTree();
printf("请输入%d的右子节点:", data);
root->right = createTree();
return root;
}
//先序遍历
void preorderTraverse(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preorderTraverse(root->left);
preorderTraverse(root->right);
}
//中序遍历
void inorderTraverse(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraverse(root->left);
printf("%d ", root->data);
inorderTraverse(root->right);
}
//后序遍历
void postorderTraverse(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraverse(root->left);
postorderTraverse(root->right);
printf("%d ", root->data);
}
//层序遍历
void levelorderTraverse(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%d ", node->data);
if (node->left) {
queue[rear++] = node->left;
}
if (node->right) {
queue[rear++] = node->right;
}
}
}
//插入节点
void insertNode(TreeNode* root, int data) {
if (root == NULL) {
return;
}
if (root->left == NULL) {
root->left = createNode(data);
} else if (root->right == NULL) {
root->right = createNode(data);
} else { //如果当前节点的左右子节点都不为空,则递归插入左右子树
insertNode(root->left, data);
insertNode(root->right, data);
}
}
//删除节点
void deleteNode(TreeNode* root, int data) {
if (root == NULL) {
return;
}
if (root->left != NULL && root->left->data == data) {
free(root->left);
root->left = NULL;
} else if (root->right != NULL && root->right->data == data) {
free(root->right);
root->right = NULL;
} else { //如果当前节点的左右子节点都不为空,则递归删除左右子树
deleteNode(root->left, data);
deleteNode(root->right, data);
}
}
//查找节点
TreeNode* searchNode(TreeNode* root, int data) {
if (root == NULL) {
return NULL;
}
if (root->data == data) {
return root;
}
TreeNode* left = searchNode(root->left, data);
TreeNode* right = searchNode(root->right, data);
if (left != NULL) {
return left;
}
if (right != NULL) {
return right;
}
return NULL;
}
//修改节点
void modifyNode(TreeNode* node, int newData) {
if (node == NULL) {
return;
}
node->data = newData;
}
int main() {
printf("请输入二叉树的根节点:");
TreeNode* root = createTree();
printf("先序遍历:");
preorderTraverse(root);
printf("\n中序遍历:");
inorderTraverse(root);
printf("\n后序遍历:");
postorderTraverse(root);
printf("\n层序遍历:");
levelorderTraverse(root);
printf("\n插入节点5后:");
insertNode(root, 5);
levelorderTraverse(root);
printf("\n删除节点5后:");
deleteNode(root, 5);
levelorderTraverse(root);
printf("\n查找节点3:");
TreeNode* node = searchNode(root, 3);
if (node != NULL) {
printf("找到了,节点的值为%d\n", node->data);
} else {
printf("没找到\n");
}
printf("修改节点3的值为10后:");
modifyNode(node, 10);
levelorderTraverse(root);
return 0;
}
```
这段代码实现了二叉树的创建、遍历、插入、删除、查找和修改等基本操作。