假设二叉排序树以后继线索链表作存储结构,用c语言编写在二叉排序树中插入一个关键字的算法
时间: 2023-11-28 11:05:26 浏览: 47
以下是使用C语言编写在二叉排序树中插入一个关键字的算法:
```c
//定义二叉排序树节点结构体
typedef struct BiTNode{
int data;
struct BiTNode *lchild, *rchild;
int ltag, rtag; //0表示指向左右孩子节点,1表示指向前驱、后继节点
}BiTNode, *BiTree;
//在二叉排序树中插入一个关键字
void insertBST(BiTree *T, int key){
if(!(*T)){ //如果二叉排序树为空,新建节点并插入
BiTree p = (BiTree)malloc(sizeof(BiTNode));
p->data = key;
p->lchild = p->rchild = NULL;
p->ltag = p->rtag = 1;
*T = p;
}
else{
if(key == (*T)->data){ //如果关键字已经存在,不插入
return;
}
else if(key < (*T)->data){ //插入到左子树
if((*T)->ltag == 0){ //如果左孩子不是前驱节点,继续递归插入
insertBST(&((*T)->lchild), key);
}
else{ //如果左孩子是前驱节点,直接插入
BiTree p = (BiTree)malloc(sizeof(BiTNode));
p->data = key;
p->lchild = (*T)->lchild;
p->rchild = (*T);
p->ltag = p->rtag = 1;
(*T)->lchild = p;
(*T)->ltag = 0;
}
}
else{ //插入到右子树
if((*T)->rtag == 0){ //如果右孩子不是后继节点,继续递归插入
insertBST(&((*T)->rchild), key);
}
else{ //如果右孩子是后继节点,直接插入
BiTree p = (BiTree)malloc(sizeof(BiTNode));
p->data = key;
p->rchild = (*T)->rchild;
p->lchild = (*T);
p->ltag = p->rtag = 1;
(*T)->rchild = p;
(*T)->rtag = 0;
}
}
}
}
```
在该算法中,我们首先判断二叉排序树是否为空,如果为空,则新建一个节点并插入。如果不为空,则判断待插入的关键字与当前节点的大小关系,如果相等,则不插入;如果小于当前节点,则插入到左子树中;如果大于当前节点,则插入到右子树中。在插入过程中,我们需要判断左孩子是否为前驱节点,右孩子是否为后继节点,如果是,则直接插入;如果不是,则继续递归插入。