node Delete(node t,int key) /*刪除函數(shù)*/{node p=t,q=NULL,s,f;while(p!=NULL) /*查找要?jiǎng)h除的點(diǎn)*/{if(p->data==key) break;q=p;if(p->data>key) p=p->lchild;else?p=p->rchild;}if(p==NULL) return t; /*查找失敗*/if(p->lchild==NULL) /*p指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)*/{if(q==NULL) t=p->rchild; /*q指向要?jiǎng)h結(jié)點(diǎn)的父母*/else if(q->lchild==p)?q->lchild=p->rchild; /*p為q的左孩子*/else q->rchild=p->rchild;/*p為q的右孩子*/free(p);}else{ /*p的左孩子不為空*/f=p;s=p->lchild;while(s->rchild) /*左拐后向右走到底*/{f=s;s=s->rchild;}if(f==p)?f->lchild=s->lchild; /*重接f的左子樹*/else?f->rchild=s->lchild; /*重接f的右子樹*/p->data=s->data;free (s);}return t;}