#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct BiTNode {//二叉链表
ElemType data;
struct BiTNode* lchild; //左指针
struct BiTNode* rchild; //右指针
} BiTNode, * BiTree;
/*
-二叉排序树：
-若它的左子树不为空, 则左子树上所有结点的值均小于它的根结构的值;
-若它的右子树不为空, 则右子树上所有结点的值大于它的根结构的值;
-它的左、右子树也分别为二叉排序树（递归）。
*/
//递归查找二叉排序树T中是否存在key
//若查找成功，则指针p指向该数据元素结点，并返回1
//否则指针p指向查找路径上访问的最后一个结点，并返回0
//f指向T的双亲，初始值值为NULL
int Search_BinarySortTree(BiTree T, int key, BiTree f, BiTree *p) {
if (!T) { //查找不成功
*p = f;
return 0;
}
else if (key == T->data) { //查找成功
*p = T;
return 1;
}
else if (key < T->data) { //在左子树继续查找
return Search_BinarySortTree(T->lchild, key, T, p);
}
else { //在右子树继续查找
return Search_BinarySortTree(T->rchild, key, T, p);
}
}
//当二叉排序树T中不存在关键字等于key的数据元素时，插入key并返回1否则返回0
//如果T为NULL；要给T根节点，所以为BiTree *T
int Insert_BinarySortTree(BiTree *T, int key) {
BiTree p, s;
if (!Search_BinarySortTree(*T, key, NULL, &p)) {
s = (BiTree)malloc(sizeof(BiTNode)); //创建一个新的节点
s->data = key;
s->lchild = s->rchild = NULL;
if (!p) { //说明没有根节点；树为空
*T = s; //插入s为新的根结点
}
else if (key < p->data) { //key小于它的的值
p->lchild = s; //s作为左子树
}
else{ //key大于它的的值
p->rchild = s; //s作为右子树
}
return 1;
}
else{
return 0; //树中已有关键字相同的结点，不再插入
}
}
//删除p节点；使用左子树的最大节点，或右子树的最小节点替换(p节点不为空)
int Delete(BiTree *p){///////////////////////////////////////////////////////////////////////////////把这个函数放前面调用它的函数前面
BiTree q; //存放要删除的节点；方便释放内存
BiTree s;
if ((*p)->rchild == NULL) { //右指针为空
q = *p;
*p = (*p)->lchild; //将左子树放在要删除的节点位置上
free(q); //释放删除的节点
}
else if ((*p)->lchild == NULL) { //左指针为空
q = *p;
*p = (*p)->rchild; //右左子树放在要删除的节点位置上
free(q); //释放删除的节点
}
else { //2个都为空;这里使用直接前驱替换(还可以使用直接后驱)
q = *p;
s = (*p)->lchild; //将左子树放在要删除的节点位置上
while (s->rchild) { //找到最右边的子树
q = s; //直接前驱的双亲
s = s->rchild;
}
//因为要保存链接，所以替换数据，删除被替换数据的节点
(*p)->data = s->data; //使用直接前驱的值替换掉p节点的值
if (q != *p) { //s是q的右子树，///////////////////////////////////////////////////////////
q->rchild = s->lchild;
}
else{ //q就是p节点，跳过s连接s->lchild
q->lchild = s->lchild;
}
free(s);
}
return 1;
}
//删除二叉排序树T中的key
int Delete_BinarySortTree(BiTree *T, int key) {
BiTree p;
if (Search_BinarySortTree(*T, key, NULL, &p)) { //找到要删除的节点
return Delete(&p);
}
else {
return 0; //树中找不到节点值为key
}
}
int main() {
return 0;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-2-25 12:45:59
置顶卡
千斤顶
显身卡
发表于 2023-2-25 19:25:05
