问答题
写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。用类Pascal(或C)语言将上述算法写为过程形式。【南开大学1998七(16分)】
【正确答案】正确答案：是二叉排序树结点的删除， while(p＆&P一>key!=x) ／／查找值为X的结点 if(p一>key>X){f=p； P=p一>lchild；} else(f=p；p=p一>rchild；} if(p==null)(Cout<<“无关键字为X的结点”<lchild=：null) ／／被删结点无左子树 if(f一>lchild：==p)f一>lchild=p一>rchild； ／／将被删结点的右子树接到其双亲上 else f一>rchild=p一>rchild; else{q=p； s=p一>lchild； ／／被删结点有左子树 while(s一>rcchild!=null) ／／查左子树中最右下的结点(中序最后结点) (q=s； s=s一>rchild；) P一>key=s一>key； ／／结点值用其左子树最右下的结点的值代替 if(q==p)P一>ichild=s一>ichild； ／／被删结点左子树的根结点无右子女 else q一>rchild：s一>ichild； ／／s是被删结点左子树中序序列最后一个结点 delete(s)； } ／／else结束，被删结点有左子树
【答案解析】