p=T->rchild q=(BiThrNode*)malloc(sizeof(BiThrNode)) T->rchild=q: T->rtag=0 q-→tag=1;q→> Achild=p,∥/修改原线索 else BSTree Insert Key(I>chid,x)/T有右子树时插入右子树中 else if(>data>x)/插入到左子树中 if(f-> lchild)/没有左子树时作为左孩子插入 q= BiThrNode*)malloc(sizeof(BiThrNode): q->data=x T->lchild=q: q→tag=lq> rchild=T,∥修改自身的线索 else BSTree Insert Key(T-> Child,x)/T有左子树时插入左子树中 J//BSTree Insert Key 9.37 Status bstree_ Delete key( BiThr Tree&r,intx∥在后继线索二叉排序树T中删除 元素x BTNode*pre,tptr;*suc:/tr为x所在结点pre和suc分别指向ptr的前驱和后继 p= T: last=NULL;∥/ast始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p-> achild;/找到中序起始元素 while(p) iflp->data=x)/找到了元素x结点 ptrp, else if((last&&last->data=x)suc=p;∥找到了x的后继 if(p->rtag) p=p->rtag, else p=p->rchild while(p->ltag)p=p->lchild 转到中序后继 [;{ p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p; //修改原线索 } else BSTree_Insert_Key(T->rchild,x);//T 有右子树时,插入右子树中 }//if else if(T->data>x) //插入到左子树中 { if(!T->lchild) //T 没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T; //修改自身的线索 } else BSTree_Insert_Key(T->lchild,x);//T 有左子树时,插入左子树中 }//if }//BSTree_Insert_Key 9.37 Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树 T 中删除 元素 x { BTNode *pre,*ptr,*suc;//ptr 为 x 所在结点,pre 和 suc 分别指向 ptr 的前驱和后继 p=T;last=NULL; //last 始终指向当前结点 p 的前一个(前驱) while(!p->ltag) p=p->lchild; //找到中序起始元素 while(p) { if(p->data==x) //找到了元素 x 结点 { pre=last; ptr=p; } else if(last&&last->data==x) suc=p; //找到了 x 的后继 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } //转到中序后继 last=p;