首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
81
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
1543年,发表了解剖学专著《人体结构》的是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
晚清时期清帝年号的正确排序是
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
随机试题
在Excel2010中,单元格的引用$E$11属于()
临床上估计肾脏的浓缩稀释功能常用的指标是
由X线管焦点辐射出的X线穿过被检体时,受到被检体各组织的吸收和散射而衰减,使透过的X线强度的分布呈现差异,到达屏—片系统,转换成可见光强度的分布差异,并传递给胶片,形成银颗粒的空间分布,再经显影处理成为二维光学分布,形成X线照片影像。决定X线“质”的因
患儿,男性,10岁。右足底被铁锈钉刺伤10天,突然张口困难,继之出现苦笑面容,角弓反张,声响及触碰患者可诱发上述症状,患者神志清楚,不发热。该病属于
在项目无资金约束、寿命不同、产出不同的条件下,方案经济比选只能采用:
在()计量下,资产按照现在购买相同或者相似资产所需支付的现金或者现金等价物的金额计量。
基金管理人应当自募集期限届满之日起()日内聘请法定验资机构验资。
在做介绍时,除女子和长者外,一般应该起立微笑致意。()
开放式最短路径优先(OSPF)中,把路由分为哪几类?
“因材施教”是学生身心发展的客观规律在教学过程中的反映。
最新回复
(
0
)