首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2017-01-04
71
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
我国对外开放格局的形成过程。
评析郑和下西洋的历史条件和意义。
比较工业革命和第二次工业革命,分析英、法、德、美工业革命的过程和特点。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
古文经学家()为了反对今文经派根据隶定的古书穿凿附会而曲解经文,于是编成一部《说文解字》,共收小篆及其他古文字9353个,逐字注释其形体音义。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
肥大心肌细胞表面积相对减少的主要危害是
患者女性,41岁。诊断为“溃疡性结肠炎”收住院,每天腹泻5~6次,有少量脓血便,对此类患者饮食护理应注意
A.肋脊角压痛、叩痛B.尿频、尿急、尿痛C.蛋白尿D.全身感染性症状E.高血压及氮质血症
A.白底绿字B.白底红字C.绿底白字D.红底白字E.黑底白字医疗用毒性药品的标签应为
中小投资者由于资金量小,一般无法购买数量众多的股票分散投资风险。基金通常会购买几十种甚至上百种股票,可以用其他股票价格上涨产生的盈利来弥补某些股票价格下跌的风险。这属于证券投资基金的()特点。
按我国企业会计准则规定,下列项目中不应确认为收入的有()。
导游服务属于有形产品范畴,有形产品具有很强的标志作用。()
单位组织慈善捐款.有同事在慈善捐款上写着“请尊重我的善心善款”o如果你负责此次捐款活动,应该怎么办?
行政成本是指政府为了社会的公共管理和为公众提供公共服务付出的代价,包括直接行政成本和间接行政成本。下列没有涉及行政成本的一项是()。
Youwillhearfivedifferentpeopletalkingaboutameetingtheyhavejustattended.Foreachextracttherearetwotasks.F
最新回复
(
0
)