二叉排序树的删除_二叉排序树的删除图示_二叉排序树删除节点(2)

3、二叉排序树的删除

在二叉排序树中删除一个结点比插入一个结点要困难，除非是叶子结点，否则必须考虑部分链的对接，以保证删除一个结点后能使剩下的结点仍是一颗二叉排序树。

假设要删除的结点为P，其双亲结点为F，且不失一般性，并设结点P是结点F的左孩子（右孩子情况类似）。如下图所示：（注：下图截至数据结构书中）。

下面分三种情况进行讨论：

（1）若P为叶子节点,删除P后只需修改双亲节点的指针即可;

（2）如果P的左子树为空或者P的右子树为空,此时只需令其左右子树PL，PR成为其双亲结点F的左右子树即可;

（3）若P的左右子树均不为空，如图8.7（a）所示：此时有两种处理方法。vcD4KPHA+ICC3vbeoMaO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu6872rULXE1/PX08r3uMTOqka1xNfz19PK96OsULXE09LX08r3uMTOqlO1xNPS19PK96O7PC9wPgo8cD4gIEYtPmxjaGlsZD1QLT5sY2hpbGQ7Uy0+cmNoaWxkPVAtPnJjaGlsZDtmcmVlKFApO73hufvI5828O3o6hjo6nL+cq+o7rS8s6qULXE09K94bXjyv0mIzIwNTQwO7HIU7XEyv0mIzIwNTQwO7Tzo6y5yrK7u+G4xLHktv6y5sXF0PLK97XE0NTWyjs8L3A+CjxwPiC3vbeoMqO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu689PDU73hteO1xCYjMjA1NDA7tPrM5lC94bXjtcQmIzIwNTQwO6Os1Nm9q1O94bXjyb6z/SzUrVO94bXjtcTX89fTyve4xM6qy6vH1zwvcD4KPHA+IL3hteNRveG147XE09LX08r3o7tQLT5kYXRhPVMtPmRhdGE7US0+cmNoaWxkPVMtPmxjaGlsZDtmcmVlKFMpoaO94bn7yOfNvDguN6OoZKOpy/nKvqGjPC9wPgo8cD6+38zly+O3qMPoyvbI58/Co7o8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">void DelBST(BSTree *t,short key){ BSTNode *p,*f,*s,*q; p=*t; f=NULL; while (p) //查找关键字为key的待删节点; { if(p->key==key){ break;} f=p; //f指向p节点的双亲节点; if(p->key>key) { p=p->lchild; } else { p=p->rchild; } } if(p==NULL)//如果没有找到直接返回; { return; } if(f==NULL)//如果p是原二叉排序树的根; { free(p); *t=NULL; return; } if(p->lchild==NULL&&p->rchild==NULL) //如果p没有左右子树; { if(f->lchild==p) { f->lchild=NULL; } else { f->rchild=NULL; } free(p); } else if(p->lchild==NULL&&p->rchild!=NULL) //如果p的左子树为空,右子树不为空; { if(f->lchild==p) { f->lchild=p->rchild; //把p的右子树链接到父亲的左链上; } else { f->rchild=p->rchild; //把p的右子树链接到父亲的右链上; } free(p); } else if(p->lchild!=NULL&&p->rchild==NULL) //如果p的左子树不为空,右子树为空; { if(f->lchild==p) { f->lchild=p->lchild; //把p的右子树链接到父亲的左链上; } else { f->rchild=p->lchild; //把p的右子树链接到父亲的右链上; } free(p); } else if(p->lchild!=NULL&&p->rchild!=NULL) //如果p的左右子树都不为空; { q=p;s=p->lchild; //s指向p的左节点; while (s->rchild) { q=s; s=s->rchild; } p->key=s->key; //把s节点的数据赋值给p节点; if(p==q) //说明待删除的p节点的左子节点下没有右结点; { q->lchild=s->lchild; //把s节点的左子树链接到q的左节点下; } else { q->rchild=s->lchild; //把s节点的左子树链接到q的右节点下; } free(s); }}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25167-2.html