首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
admin
2019-08-01
82
问题
设排序二叉树中结点的结构由三个域构成:数据域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 p=T,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/t3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在西欧列强海外殖民扩张进程中,各国之间相互争夺海上霸权。18世纪末,英国在争霸中取得胜利的根本原因在于()
中国民族工业产生后,多集中于沿海地区,其主要原因是()。
试论中国古代经济重心南移的过程。
晚清时期清帝年号的正确排序是
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
科学社会主义产生的直接思想来源是()。
提出“天有常道,地有常数”,“制天命而用之”的思想家是()。
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
在一个按字节编址的计算机中,若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H,i的机器数为01234567H,地址:08000000H单元的内容是()。
随机试题
湿式、干式自动喷水灭火系统中,公称直径大于或等于100mm的管道,其距离顶板、墙面的安装不宜小于()mm。
设函数y=cos(lnx),求y′.
简述心室肌细胞动作电位的产生机制。
初孕妇,头位,宫口开全2小时,S+1,LOT,胎心110次/min,宫缩持续25秒,间隔4~5分钟,羊水Ⅱ度混浊。最佳的处理方法是
式
甲欲开枪杀乙,射击的结果却是导致乙重伤,同时导致乙身边的丙死亡。关于本案,下列哪些说法是错误的?
下列属于设计人的违约责任的选项有( )。
我国境内的股票价格指数不包括()。
下列哪个选项属于教育的基本要素?()
资产评估的经济技术原则有哪些?
最新回复
(
0
)