二叉排序树的c语言代码
- 格式：doc
- 大小：11.32 KB
- 文档页数：2
二叉排序树（Binary Sort Tree）是一种特殊的二叉树，它或左子树或右子树为完全二叉树。由于二叉排序树的特点，其每个节点的值均大于其左子树中的所有节点的值，且小于其右子树中的所有节点的值。
以下是一个简单的二叉排序树的C语言实现，包括插入、查找和删除操作。
```c
#include
#include
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
// 创建一个新的节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("内存分配失败\n");
return NULL;
}
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 在二叉排序树中插入一个新的节点
Node* insert(Node* root, int data) {
if (!root) { // 如果树为空，创建新节点并返回根节点
root = createNode(data);
} else if (data <= root->data) { // 如果插入的数据小于当前节点的值，则在左子树中插入
root->left = insert(root->left, data);
} else { // 如果插入的数据大于当前节点的值，则在右子树中插入
root->right = insert(root->right, data);
}
return root; // 返回插入后的根节点
}
// 在二叉排序树中查找一个值是否存在
int search(Node* root, int data) { if (!root) { // 如果树为空，返回0表示未找到
return 0;
} else if (root->data == data) { // 如果找到，返回1表示找到
return 1;
} else if (data < root->data) { // 如果插入的数据小于当前节点的值，在左子树中查找
return search(root->left, data);
} else { // 如果插入的数据大于当前节点的值，在右子树中查找
return search(root->right, data);
}
}
// 在二叉排序树中删除一个节点，并返回被删除的节点指针（如果存在）
Node* deleteNode(Node* root, int data) {
if (!root) return NULL; // 如果树为空，直接返回NULL（空树）
if (data < root->data) { // 如果要删除的值小于当前节点的值，则在左子树中查找并删除
root->left = deleteNode(root->left, data);
} else if (data > root->data) { // 如果要删除的值大于当前节点的值，则在右子树中查找并删除
root->right = deleteNode(root->right, data);
} else { // 如果要删除的节点就是当前节点，根据情况选择删除方式（左子树或右子树）
if (root->left == NULL) { // 如果左子树为空，直接删除当前节点（只有根节点时）
Node *temp = root; // 临时保存当前节点，用于释放内存后替换原节点指针为NULL
free(temp); // 释放内存空间后将原指针设为NULL
} else if (root->right == NULL) { // 如果右子树为空，直接删除当前节点（只有一个节点时）
Node *temp = root->left; // 临时保存左子树的根节点，用于替换原节点指针为左子树的根节点指针（此时原节点为空）
free(root); // 释放原节点的内存空间后将原指针设为NULL（此时原节点为空）
root = temp; // 将原指针设为新的根节点指针（此时原节点为空）
} else { // 如果左右子树都存在，则找到右子树中的最小节点（即要被替换的节点），替换原节点指针为最小节点的指针（此时原节点为空）并删除最小节点（通过递归实现）
Node *temp = root->right; // 临时保存右子树的根节点指针（即要被替换的节点）
root->data = temp->data; // 将原节点的数据
