首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
72
问题
设排序二叉树中结点的结构由三个域构成:数据域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一>right;free(p);} } }//DelTree void DeleteAllx(BSTree T,int x){ //在二叉排序树T中,删除所有小于等于x的结点 BSTree =pT,q; while(T&&T->data<=x){ //根结点的值小于等于x p=T;T=T一>right;p一>right=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一>right;p一>right=null;DelTree(p); } p=q->left; //再查原p的右子树中小于等于x的结点 } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/JMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
关于B一树,下列说法不正确的是()。
关于B一树,下列说法中不正确的是()。
关于B一树,下列说法中不正确的是()。
随机试题
下列哪项评价的是明代作家宋濂()
下列采用普通法系的国家是【 】
我国文学史上第一部诗歌总集是______。
A、二阴煎B、养心汤C、大补元煎D、左归丸E、滋水清肝饮癫证心脾两虚型宜选用
时距是一项工作的最早开始或完成时间与另一工作的最早开始或完成时间之间的时间间隔以下说法不正确的是()。
2014年甲村水稻亩产400公斤,乙村水稻亩产800公斤。因为乙村使用了杂交水稻新品种,所以人们认为乙村水稻亩产量高可能是使用了新品种的缘故。能给上述论述提供最有力支持的一项是:
人生观的作用主要通过人生目的、人生态度、人生价值三个方面体现出来。人生目的回答人为什么活着,人生态度表明人应当怎样对待生活,人生价值判断什么样的人生才有意义。这三个方面互相联系、互相制约,其中居于核心地位的是()
某企业采用Windows2000操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2000操作系统当中对IPSec具备完善的支持,图13-3给出了基于Windows2000系统部署
下面是关于ARM嵌入式芯片中的DMA控制器的叙述,其中错误的是()。
Everypersonplanstorunofftosometropicalisle,butfewdo.Reallife,family,work,andmonetarylimitationsgetinthewa
最新回复
(
0
)