int DeleteBST(BSTNode *&bt,KeyType k) { /********** Begin **********/ /********** End **********/ }
时间: 2023-11-25 19:51:05 浏览: 51
以下是实现二叉排序树节点删除的代码,其中bt为指向二叉排序树的指针,k为要删除的节点的键值:
```c
int DeleteBST(BSTNode *&bt,KeyType k) {
if (!bt) return 0; // 如果树为空,返回0
else {
if (k == bt->key) { // 如果找到了要删除的节点
BSTNode *p = bt;
if (bt->lchild == NULL) { // 如果要删除的节点没有左子树
bt = bt->rchild;
free(p);
}
else if (bt->rchild == NULL) { // 如果要删除的节点没有右子树
bt = bt->lchild;
free(p);
}
else { // 如果要删除的节点既有左子树又有右子树
BSTNode *s = bt->lchild;
while (s->rchild) s = s->rchild; // 找到要删除节点的左子树中的最大节点
bt->key = s->key; // 用最大节点的键值替换要删除节点的键值
DeleteBST(bt->lchild, s->key); // 删除最大节点
}
return 1;
}
else if (k < bt->key) return DeleteBST(bt->lchild, k); // 如果要删除的节点在左子树中
else return DeleteBST(bt->rchild, k); // 如果要删除的节点在右子树中
}
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](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)