C语言实现二叉排序树
时间: 2023-12-10 12:33:03 浏览: 32
二叉排序树是一种特殊的二叉树,它的左子树中所有节点的值都小于根节点的值,右子树中所有节点的值都大于根节点的值。C语言实现二叉排序树需要以下几个步骤:
1. 定义二叉排序树的结构体,包括节点的值和左右子树指针。
```c
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
```
2. 实现二叉排序树的插入操作,将新节点插入到合适的位置。
```c
BSTNode* insert(BSTNode *root, int data) {
if (root == NULL) {
root = (BSTNode*)malloc(sizeof(BSTNode));
root->data = data;
root->left = NULL;
root->right = NULL;
} else if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
```
3. 实现二叉排序树的查找操作,查找指定值的节点。
```c
BSTNode* search(BSTNode *root, int data) {
if (root == NULL || root->data == data) {
return root;
} else if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
```
4. 实现二叉排序树的删除操作,删除指定值的节点。
```c
BSTNode* delete(BSTNode *root, int data) {
if (root == NULL) {
return root; } else if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(root->right, data);
} else {
if (root->left == NULL) {
BSTNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
BSTNode *temp = root->left;
free(root);
return temp;
}
BSTNode *temp = minValueNode(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}
```
5. 实现查找二叉排序树中最小值节点的函数。
```c
BSTNode* minValueNode(BSTNode *node) {
BSTNode *current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
```