首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2017-01-04
66
问题
设排序二叉树中结点的结构由三个域构成:数据域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://kaotiyun.com/show/lQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析商代的阶级关系。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
最早以立法形式巩固大化改新成果的法令是()。
下列哪一项不是凯末尔世俗化改革的内容?()
下列不是唐玄宗组织编撰的是()。
红山文化的代表性墓葬形式为()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
四位运算器框图如图6—2所示,ALU为算术逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的SW门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1(A
随机试题
蛛网膜下腔出血最常见的原因是
某软件公司规模不断发展壮大,员工人数已从原来的20多人增加到现在的400多人,但管理层却发现公司的工作效率明显地下降了,相同类型的项目,过去5个人1个月可以完成,而现在10个人1个月都完成不了。由于绩效降低,员工人心涣散。[2005年真题]如果要改变这
广州圣心大教堂,始建于清同治二年(1863年),由法国普行善会建造,属法国哥特式建筑,高()米,是国内最大的哥特式教堂之一。
试分析达.芬奇的作品《蒙娜丽莎》。
A.RPI卡环B.回力卡环C.联合卡环D.对半卡环E.杆形卡环具有应力中断作用()。
Thenewprisonisdesignedparticularlyfor______.
WhatdoesthenewsitemsayaboutChristineLagarde?
PASSAGETHREEAccordingtothepassage,whatwillforgivenessleadto?
[A]advocates[B]approaching[C]constantly[D]decrease[E]enlarge[F]financial[G]fundamental[H]gracious[I]ignored[J]intention[K]just
A.inappropriateB.attendC.slipsD.trackE.financeF.unchangeableG.organize
最新回复
(
0
)