二叉查找树的删除逻辑
时间: 2024-06-15 17:06:19 浏览: 46
二叉查找树(Binary Search Tree,BST)的删除逻辑如下:
1. 首先,需要找到要删除的节点。从根节点开始,比较要删除的值与当前节点的值大小关系,如果相等,则找到了要删除的节点;如果要删除的值小于当前节点的值,则继续在当前节点的左子树中查找;如果要删除的值大于当前节点的值,则继续在当前节点的右子树中查找。
2. 找到要删除的节点后,需要考虑以下三种情况进行处理:
- 如果要删除的节点是叶子节点(没有子节点),直接删除即可。
- 如果要删除的节点只有一个子节点,将其子节点替代该节点的位置。
- 如果要删除的节点有两个子节点,需要找到该节点的后继节点或前驱节点来替代该节点。后继节点是指比要删除的节点大的最小节点,前驱节点是指比要删除的节点小的最大节点。可以选择使用后继节点或前驱节点来替代要删除的节点。
3. 替代要删除的节点后,需要更新树的结构,使其仍然满足二叉查找树的性质。具体操作如下:
- 如果要删除的节点是根节点,则直接用替代节点替换根节点。
- 如果要删除的节点是其父节点的左子节点,则将替代节点连接到其父节点的左子节点。
- 如果要删除的节点是其父节点的右子节点,则将替代节点连接到其父节点的右子节点。
4. 最后,删除完成后,需要释放被删除节点的内存空间。
相关问题
用二叉排序树写通讯录管理系统
二叉排序树是一种基于二叉树的数据结构,它的每个节点都有一个关键字,而且左子树上的所有节点的关键字都小于父节点的关键字,右子树上的所有节点的关键字都大于父节点的关键字。这样,我们可以通过比较节点的关键字来快速查找、插入和删除数据。在通讯录管理系统中,我们可以使用二叉排序树来实现联系人的添加、查找和删除操作。
首先,我们需要定义二叉排序树的节点结构体:
```c++
typedef struct TreeNode {
string name; // 联系人姓名
string tel; // 联系人电话
struct TreeNode *left; // 左子树
struct TreeNode *right; // 右子树
} TreeNode, *Tree;
```
然后,我们可以定义一些辅助函数,比如创建节点、插入节点、查找节点等:
```c++
// 创建节点
Tree createNode(string name, string tel) {
Tree node = new TreeNode;
node->name = name;
node->tel = tel;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
Tree insertNode(Tree root, string name, string tel) {
if (root == NULL) {
return createNode(name, tel);
}
if (name < root->name) {
root->left = insertNode(root->left, name, tel);
} else if (name > root->name) {
root->right = insertNode(root->right, name, tel);
} else {
// 如果姓名已经存在,则更新电话号码
root->tel = tel;
}
return root;
}
// 查找节点
Tree searchNode(Tree root, string name) {
if (root == NULL || root->name == name) {
return root;
}
if (name < root->name) {
return searchNode(root->left, name);
} else {
return searchNode(root->right, name);
}
}
```
接下来,我们可以定义一些用户界面函数,比如添加联系人、查找联系人、删除联系人等:
```c++
// 添加联系人
void addContact(Tree &root) {
string name, tel;
cout << "请输入联系人姓名:";
cin >> name;
cout << "请输入联系人电话:";
cin >> tel;
root = insertNode(root, name, tel);
cout << "添加成功!" << endl;
}
// 查找联系人
void searchContact(Tree root) {
string name;
cout << "请输入要查找的联系人姓名:";
cin >> name;
Tree node = searchNode(root, name);
if (node == NULL) {
cout << "未找到联系人!" << endl;
} else {
cout << "联系人姓名:" << node->name << endl;
cout << "联系人电话:" << node->tel << endl;
}
}
// 删除联系人
Tree deleteNode(Tree root, string name) {
if (root == NULL) {
return root;
}
if (name < root->name) {
root->left = deleteNode(root->left, name);
} else if (name > root->name) {
root->right = deleteNode(root->right, name);
} else {
// 找到要删除的节点
if (root->left == NULL) {
Tree temp = root->right;
delete root;
return temp;
} else if (root->right == NULL) {
Tree temp = root->left;
delete root;
return temp;
}
Tree temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->name = temp->name;
root->tel = temp->tel;
root->right = deleteNode(root->right, temp->name);
}
return root;
}
void removeContact(Tree &root) {
string name;
cout << "请输入要删除的联系人姓名:";
cin >> name;
Tree node = searchNode(root, name);
if (node == NULL) {
cout << "未找到联系人!" << endl;
} else {
root = deleteNode(root, name);
cout << "删除成功!" << endl;
}
}
```
最后,我们可以定义一个主函数,来实现整个程序的逻辑:
```c++
int main() {
Tree root = NULL;
int choice;
while (true) {
cout << "通讯录管理系统" << endl;
cout << "1. 添加联系人" << endl;
cout << "2. 查找联系人" << endl;
cout << "3. 删除联系人" << endl;
cout << "4. 退出系统" << endl;
cout << "请选择操作:";
cin >> choice;
switch (choice) {
case 1:
addContact(root);
break;
case 2:
searchContact(root);
break;
case 3:
removeContact(root);
break;
case 4:
exit(0);
break;
default:
cout << "无效操作!" << endl;
break;
}
}
return 0;
}
```
这样,我们就完成了一个基于二叉排序树的通讯录管理系统。用户可以通过菜单来进行添加、查找和删除联系人等操作。
物理数据结构和逻辑数据结构
物理数据结构和逻辑数据结构是数据结构中的两个重要概念。物理数据结构指的是数据在计算机内存中的存储方式,包括顺序存储和链式存储;逻辑数据结构指的是数据之间的逻辑关系,包括线性结构、树形结构、图形结构等。
线性结构是一种简单的逻辑数据结构,它包括线性表、栈、队列等。线性表是最基本的线性结构,它可以用顺序存储和链式存储两种方式实现。栈和队列是线性表的特殊形式,它们分别具有后进先出和先进先出的特点。
树形结构是一种非线性的逻辑数据结构,它包括二叉树、平衡树、B树等。二叉树是最基本的树形结构,它每个节点最多只有两个子节点。平衡树是一种自平衡的二叉搜索树,它可以保证在插入和删除操作后仍然保持平衡。B树是一种多路搜索树,它可以在磁盘等外部存储设备上高效地进行查找操作。
图形结构是一种复杂的逻辑数据结构,它包括有向图和无向图。有向图中每个节点都有一个方向,而无向图中每个节点之间没有方向。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)