已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子。试编写算法,删除p所指结点。

admin2019-08-01  50

问题 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子。试编写算法,删除p所指结点。

选项

答案本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。 w)id Delete(BSTree bst,P,fp){ //在二叉排序树bst上,删除fp所指结点的左子女(由P所指向) if(!p一>lchild){fp一>lchild=p一>rchild;free(P);} //p无左子女 else if(!p一>rchild){fp一>lchild=p一>lehild;flee(P);} //p无右子女 else //P有左子女和右子女 {q=P一>rchild;s=q; //用P右子树中的最小值代替P结点的值 while(q一>lchild){S=q;q=q一>lchild;} //查P右子树中序序列最左结点 if(S==p一>rehild) //p右子树的根结点无左子女 {p一>data=s一>data;p一>rchild=s一>rchild;frees);} else{p一>data=q一>data;s一>lchild=q一>rchild;free(q);} } }

解析
转载请注明原文地址:https://kaotiyun.com/show/FjCi777K
0

随机试题
最新回复(0)