首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2017-01-04
79
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
西汉初年,在刘邦翦灭异姓诸侯王的过程中,被保留下来的异姓诸侯王是()
简述士族的源流和在西晋的发展过程。
下列对春秋时期各国称霸的顺序描述错误的选项是()
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
下列制度不是战国时代开始推行的是()。
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
随机试题
_______在汽车行驶过程中一直工作,在驱动轮出现滑转时起作用。
已知,求下图所示梁内D点的竖向位移。
川芎的功效为活血行气
1岁半小儿,食欲差,智力落后,出牙2颗,身高70cm,前囟1×1cm,家人要求补钙治疗。你认为应首先做下列哪项检查最有助于诊断
有关交易所席位的说法,正确的是()。
简述班主任应如何做好后进生的工作。
下列关于我国脱贫攻坚工作说法准确的是:
下列技术中,(17)实现用一类物理设备模拟另一类物理设备,同时也实现速度匹配。
请使用VC6或使用【答题】菜单打开考生文件夹proj1下的工程proj1,该工程中包含程序文件main.cpp,其中有关TVSet(“电视机”)和主函数main的定义。程序中位于每个“//ERROR***********found***********”之
许多人外出逛街、游玩时,会【149】灵活机动的自行车作为代步【150】,时尚的双人、三人骑自行车尤其受到青年人的青睐。于是,自行车出租业也就应运而生了。要骑自行车的人,需【151】身份证租车。对于城市人来说,毕竟花钱去健身房不如旅游式的自行车运动
最新回复
(
0
)