2. 考研
  3. 设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。

设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。

admin2017-01-04  84
问题 设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。
选项
答案利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。 typedef struct node{ int data； struct node*left * right： }BiTNode，* BSTree； void DelTree(BSTree r){ ／／非递归删除以r为根的二叉排序树 BSTree S[]； ／／栈，容量足够大，栈中元素是二叉排序树结点的指针 BSTree P； int top=0； while(r!=null || top＞0){ while(r!=null){S[++top]=r；r=r一＞left；} ／／沿左分支向下 if(top＞0) ／／退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 {p=S[top一一]；r=p一＞fight；free(P)；} } }／／DelTree void DeleteAllx(BSTree T，int X){ ／／在二叉排序树T中，删除所有小于等于X的结点 BSTree P=T，q； while(T&＆T-＞data＜=x){ ／／根结点的值小于等于x P=T；T=T一＞fight；p一＞fight=null； DelTree(P)； } ／／删除二叉树P，删除持续到”根”结点值大于x或T为空树为止 if(T){ q=T；P=T一＞left； while(P&&P一＞data>x){ ／／沿根结点左分支向下，查小于等于x的结点 while(P＆&p一＞data＞x){q=p；p=p一＞left；} ／／q记P的双亲 if(P) ／／p结点的值小于等于X { q一＞left=p一＞fight；p一＞fight=null；DelTree(P)； } P=q一＞left； ／／再查原P的右子树中小于等于X的结点 } } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/lQRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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