二叉排序树删除结点程序填空
时间: 2023-08-21 07:20:24 浏览: 52
以下是实现二叉排序树删除结点程序的完整代码,包含了详细的注释:
```c++
#include <iostream>
using namespace std;
typedef struct ElemType {
int key;
} ElemType;
typedef struct BSTNode {
ElemType data;
BSTNode* lchild, * rchild;
} BSTNode, * BSTree;
int flag = 1;
// 插入节点
void InsertBST(BSTree& T, ElemType e);
// 创建二叉排序树
void CreateBST(BSTree& T);
// 中序遍历
void InOrderTraverse(BSTree T);
// 删除节点
void DeleteBST(BSTree& T, char key);
int main() {
BSTree T;
CreateBST(T);
int key;
cin >> key;
DeleteBST(T, key);
InOrderTraverse(T);
}
void InsertBST(BSTree& T, ElemType e) {
if (!T) {
T = new BSTNode;
T->data = e;
T->lchild = T->rchild = NULL;
return;
}
if (e.key == T->data.key) {
flag = 0;
return;
}
else if (e.key < T->data.key) {
InsertBST(T->lchild, e);
}
else {
InsertBST(T->rchild, e);
}
}
void CreateBST(BSTree& T) {
T = NULL;
int n;
cin >> n;
ElemType e;
for (int i = 0; i < n; i++) {
cin >> e.key;
flag = 1;
InsertBST(T, e);
}
}
void InOrderTraverse(BSTree T) {
if (T) {
InOrderTraverse(T->lchild);
cout << T->data.key << " ";
InOrderTraverse(T->rchild);
}
}
void DeleteBST(BSTree& T, char key) {
if (!T) { // 未找到节点
return;
}
if (T->data.key == key) { // 找到待删除节点
BSTree p = T;
// 待删除节点左右子树都不为空
if (T->lchild && T->rchild) {
BSTree q = T->lchild;
while (q->rchild) {
q = q->rchild;
}
T->data = q->data;
DeleteBST(T->lchild, q->data.key);
}
else { // 待删除节点左右子树至少有一个为空
if (!T->lchild) { // 只有右子树
T = T->rchild;
}
else if (!T->rchild) { // 只有左子树
T = T->lchild;
}
delete p;
}
}
else if (T->data.key > key) { // 在左子树中查找
DeleteBST(T->lchild, key);
}
else { // 在右子树中查找
DeleteBST(T->rchild, key);
}
}
```
在DeleteBST函数中,首先判断当前节点是否为待删除节点,如果是,则分情况处理:
1. 待删除节点左右子树都不为空:找到待删除节点左子树中最大的节点,用其代替待删除节点,然后删除该节点。
2. 待删除节点左右子树至少有一个为空:将待删除节点的父节点指向待删除节点的非空子树,然后删除待删除节点。
如果当前节点不是待删除节点,则根据二叉排序树的性质在左右子树中查找待删除节点,直到找到待删除节点或者遍历完整个二叉排序树为止。