数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中的二叉搜索树 - 删除操作
二叉搜索树 (BST) 是一种特殊的树，它遵循以下规则：
左子节点的值始终小于父节点
右子节点的值始终大于父节点。
所有节点都各自构成一个二叉搜索树。
二叉搜索树 (BST) 示例：
创建二叉搜索树是为了降低搜索、查找最小值和最大值等操作的复杂度。
二叉搜索树 (BST) 的删除操作
删除操作是从树中删除指定的节点。在删除节点时，有三种可能性：
从树中删除叶子节点：最简单的删除是从二叉搜索树中删除叶子节点。删除叶子节点只会影响叶子节点本身。例如：
删除叶子节点 7 得到：
删除只有一个子节点的节点：对于此删除操作，需要用要删除的节点的子节点替换该节点，然后删除该节点。例如：
从 BST 中删除 2
删除有两个子节点的节点：此处要删除的节点有两个子节点。因此，我们将使用树的中序遍历形式，在这里我们将删除该元素并选择其中序邻接节点来代替它，然后重建其余部分。例如：
从 BST 中删除 5 将返回以下树。
示例
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inordertraversal(struct node *root){
if (root != NULL){
inordertraversal(root->left);
printf("%d ", root->key);
inordertraversal(root->right);
}
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
struct node * minValueNode(struct node* node){
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key){
if (root == NULL) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else{
if (root->left == NULL){
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL){
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main(){
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Inorder traversal of the given tree \n");
inordertraversal(root);
printf("\nDelete 20\n");
root = deleteNode(root, 20);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 30\n");
root = deleteNode(root, 30);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 50\n");
root = deleteNode(root, 50);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
return 0;
}输出
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
更新于：2020年1月3日
4K+ 次浏览
广告