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

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

admin2019-01-16  74
问题 二叉排序树采用二叉链表存储。写一个算法，删除结点值是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-＞lehild；} else{f=p；P=p一＞rehild；} if(P==null){prinff(”无关键字为x的结点＼n”)；exit(0)：} if(p-＞lchild==null){ ／／被删结点无左子树 if(f一＞lchild==P)f一＞lchild=P一＞rchild；／／将被删结点的右子树接到其双亲上 else f一＞rchild=p一＞rchild； } else{q=p；s=p-＞lchild； ／／被删结点有左子树 while(s-＞rchild!=null) ／／查左子树中最右下的结点(中序最后结点) {q=s；s=s-＞rchild；} p-＞key=s-＞key； ／／结点值用其左子树最右下的结点的值代替 if(q==p)p一＞lchild=s一＞lchild； ／／被删结点左子树的根结点无右子女 else q-＞rchild=s-＞lchild： ／／s是被删结点左子树中序序列最后一个结点 free(s)； } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/llRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)