用C语言写一个中文的关于二叉树所有操作的程序并注释
时间: 2024-05-24 12:12:35 浏览: 8
// 以下是一个中文的关于二叉树所有操作的程序
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int data; // 节点的数据
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
} TreeNode, *Tree;
// 创建一个新节点
TreeNode* create_node(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
void insert_node(Tree* tree, int data) {
if (*tree == NULL) { // 如果二叉树为空,则直接插入节点
*tree = create_node(data);
} else { // 否则,根据大小比较插入左或右子树
if (data < (*tree)->data) {
insert_node(&((*tree)->left), data);
} else {
insert_node(&((*tree)->right), data);
}
}
}
// 查找节点
TreeNode* find_node(Tree tree, int data) {
if (tree == NULL) { // 如果二叉树为空,则返回NULL
return NULL;
} else if (data == tree->data) { // 如果找到了节点,则返回该节点
return tree;
} else if (data < tree->data) { // 如果要查找的节点比当前节点小,则在左子树中继续查找
return find_node(tree->left, data);
} else { // 否则,在右子树中查找
return find_node(tree->right, data);
}
}
// 获取最小节点
TreeNode* get_min_node(Tree tree) {
if (tree == NULL) { // 如果二叉树为空,则返回NULL
return NULL;
} else if (tree->left == NULL) { // 如果当前节点没有左子节点,则当前节点就是最小节点
return tree;
} else { // 否则,在左子树中继续查找最小节点
return get_min_node(tree->left);
}
}
// 删除节点
void delete_node(Tree* tree, int data) {
if (*tree == NULL) { // 如果二叉树为空,则直接返回
return;
} else if (data < (*tree)->data) { // 如果要删除的节点比当前节点小,则在左子树中继续删除
delete_node(&((*tree)->left), data);
} else if (data > (*tree)->data) { // 否则,在右子树中删除
delete_node(&((*tree)->right), data);
} else { // 找到了要删除的节点
if ((*tree)->left == NULL && (*tree)->right == NULL) { // 如果该节点没有子节点,则直接删除
free(*tree);
*tree = NULL;
} else if ((*tree)->left == NULL) { // 如果只有右子节点,则用右子节点替换当前节点
Tree temp = *tree;
*tree = (*tree)->right;
free(temp);
} else if ((*tree)->right == NULL) { // 如果只有左子节点,则用左子节点替换当前节点
Tree temp = *tree;
*tree = (*tree)->left;
free(temp);
} else { // 如果当前节点既有左子节点又有右子节点,则用右子树中的最小节点替换当前节点
TreeNode* min_node = get_min_node((*tree)->right);
(*tree)->data = min_node->data;
delete_node(&((*tree)->right), min_node->data);
}
}
}
// 遍历二叉树(中序遍历)
void traverse(Tree tree) {
if (tree == NULL) { // 如果二叉树为空,则直接返回
return;
}
traverse(tree->left); // 遍历左子树
printf("%d ", tree->data); // 输出当前节点的数据
traverse(tree->right); // 遍历右子树
}
int main() {
Tree tree = NULL; // 定义一个空的二叉树
insert_node(&tree, 5);
insert_node(&tree, 2);
insert_node(&tree, 7);
insert_node(&tree, 1);
insert_node(&tree, 3);
insert_node(&tree, 6);
insert_node(&tree, 8);
printf("中序遍历二叉树:");
traverse(tree);
printf("\n");
TreeNode* node = find_node(tree, 3);
if (node != NULL) {
printf("找到了节点:%d\n", node->data);
} else {
printf("没有找到节点\n");
}
delete_node(&tree, 5);
printf("删除节点后的中序遍历二叉树:");
traverse(tree);
printf("\n");
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)