二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。

admin2019-08-01  42

问题 二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。

选项

答案在二叉排序树上删除结点,首先要查找该结点。查找成功后,若该结点无左子树,则可直接将其右子树的根结点接到其双亲结点上;若该结点有左子树,则将其左子树中按中序遍历的最后一个结点代替该结点,从而不增加树的高度。 void Delete(BSTree bst,keytype X){ //在二叉排序树bst上,删除其关键字为X的结点 BSTree f,p=bst: while(P&&p一>key!=X) //查找值为X的结点 if(p一>key>X){f=P;P=p一>lchild;} else{f=P;P=p一>rchild;} if(P==null){printf(”无关键字为x的结点\n”);exit(0);} if(p一>lchild==null){ //被删结点无左子树 if(f一>lchild==P)f一>lehild=P一>rchild;//将被删结点的右子树接到其双亲上 else f一>rchild=p一>rehild; } else{q=P;s=p一>lehild; //被删结点有左子树 while(S->rehild!=null) //查左子树中最右下的结点(中序最后结点) {q=s;s=s一>rehild;} P一>key=s一>key; //结点值用其左子树最右下的结点的值代替 if(q==P)P一>lchild=s一>lchild; //被删结点左子树的根结点无右子女 else q一>rchild=s一>lchild; //s是被删结点左子树中序序列最后一个结点 free(s); } }

解析
转载请注明原文地址:https://jikaoti.com/ti/kDGjFFFM
0

最新回复(0)