C语言二叉排序树的建立,插入,删除,树形打印显示代码,并给出详细解释步骤
时间: 2024-05-06 10:20:27 浏览: 44
C语言编写的二叉排序树的插入、删除
4星 · 用户满意度95%
1. 二叉排序树的建立
```
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
Node *createBST(int *arr, int n) {
Node *root = NULL;
for (int i = 0; i < n; i++) {
root = insertBST(root, arr[i]);
}
return root;
}
Node *insertBST(Node *root, int data) {
if (root == NULL) {
root = (Node *)malloc(sizeof(Node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
if (data < root->data) {
root->left = insertBST(root->left, data);
}
else {
root->right = insertBST(root->right, data);
}
return root;
}
```
二叉排序树的建立是通过不断地插入节点来实现的,如果根节点为空,那么直接将新节点插入到根节点;如果新节点的值小于根节点的值,那么递归插入到左子树中;如果新节点的值大于等于根节点的值,那么递归插入到右子树中。
2. 二叉排序树的插入
```
Node *insertBST(Node *root, int data) {
if (root == NULL) {
root = (Node *)malloc(sizeof(Node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
if (data < root->data) {
root->left = insertBST(root->left, data);
}
else {
root->right = insertBST(root->right, data);
}
return root;
}
```
二叉排序树的插入与建立相似,只需要在找到合适的叶子节点后插入新节点即可。
3. 二叉排序树的删除
```
Node *deleteBST(Node *root, int data) {
if (root == NULL) {
return NULL;
}
if (data < root->data) {
root->left = deleteBST(root->left, data);
}
else if (data > root->data) {
root->right = deleteBST(root->right, data);
}
else {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
else if (root->left == NULL) {
Node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
Node *temp = root->left;
free(root);
return temp;
}
else {
Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteBST(root->right, temp->data);
}
}
return root;
}
Node *findMin(Node *root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
```
二叉排序树的删除有三种情况,分别是删除叶子节点、删除只有一个子节点的节点和删除有两个子节点的节点。对于第一种情况,直接删除即可;对于第二种情况,将子节点替换父节点即可;对于第三种情况,找到右子树中最小的节点替换要删除的节点,然后再递归删除右子树中的最小节点即可。
4. 二叉排序树的树形打印显示
```
void printBST(Node *root, int level) {
if (root == NULL) {
return;
}
printBST(root->right, level + 1);
for (int i = 0; i < level; i++) {
printf(" ");
}
printf("%d\n", root->data);
printBST(root->left, level + 1);
}
```
二叉排序树的树形打印显示可以先递归右子树,然后输出当前节点,最后再递归左子树。为了保持树的形状,需要在输出当前节点前输出一定数量的空格,使得当前节点在对称轴上。
阅读全文