首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2017-01-04
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一>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
学硕统考专业
相关试题推荐
春秋时期封建生产关系是怎样产生的?
英国封建制度形成的过程。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
葡萄牙、西班牙最早走上殖民征服道路,从政治上来说是由于()
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
红山文化的代表性墓葬形式为()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
利用栈求表达式的值时,设立运算数栈OPND。假设OPND只有两个存储单元,在下列表达式中,不发生溢出的是()。
随机试题
【案例】患者男,65岁。诊断为肺炎入院,应用抗生素治疗后未见好转,3天后突然出现呼吸急促,烦躁,出大汗。体检:呼吸42次/分,血压98/70mmHg,脉搏102次/分,口唇发绀,双肺闻及水泡音。呼吸衰竭患者气管插管或气管切开的适应证是
下列各句中,加着横线的词属于范围副词的一句是【】
对鼓膜传音功能不正确的叙述是
A.语音嘶哑B.语音重浊C.声高息粗D.声微息弱E.语言流利
进口设备检验鉴定费属于()。
“磁盘碎片整理程序”所具有的功能有()。
图文混排是Word的特色功能之一。下列表述中,不正确的是()。
如果有2000比特的数据通过一个1Mbps的网卡进行传输,所产生的发送时延是()。
数据库系统中可能会发生各种各样的故障。这些故障主要有四类,即:事务故障、系统故障、介质故障和【】。
TheAmericanfarmershavealwaysbeenindependentandhard-working.Intheeighteenthcenturyfarmerswerequiteself-sufficien
最新回复
(
0
)