首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2019-01-16
19
问题
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。
设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于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/SlRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在下列各项中,不属于列宁《四月提纲》内容的是()。
范仲淹在《答手诏条陈十事》中提出,庆历新政的核心内容是()。
以下不属于国民党控制金融的“四行”的是()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
下列哪一个不是罗马王政时代的管理机构?()
洋务派创办军事工业的方式是()。
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
不需要抢占的进程调度算法是()。
随机试题
A、具有抑菌作用的药物B、烷化剂类抗肿瘤药C、具有抗肿瘤作用的生物碱D、抗艾滋病药物E、具有抗肿瘤作用的嘧啶类衍生物卡莫司汀为
A、葡萄糖-6-磷酸酶B、磷酸烯醇式丙酮酸羧激酶C、丙酮酸激酶D、果糖二磷酸酶E、丙酮酸羧化酶以上是糖异生的关键酶,但除外()
临床窝沟封闭术失败的原因最主要是
石灰粉煤灰稳定类基料用作二级和二级以下公路基层时,对压实度(按重型击实标准)的要求为()。
测算股价与移动平均线偏离程度的指标是()。
大华股份有限公司(以下简称大华公司)为上市公司,系增值税一般纳税人,适用的增值税税率为17%;产品的销售价格中均不含增值税额;不考虑除增值税以外的其他相关税费。大华公司2005年发生的有关交易如下:(1)2005年1月1日,大华公司与A公司签订受
甲股份有限公司(以下简称甲公司)为上市公司,适用的所得税税率为25%。为提高市场占有率及实现多元化经营,甲公司从2015年开始进行了一系列投资和资本运作。有关资料如下。(1)甲公司于2015年1月1日,以900万元银行存款取得乙公司20%的普通股份,
清楚的通道、干净的地板、适当且有次序的储存及安全的运行,也是良好仓储管理所关心的问题。()
上海世博会园80%的夜景照明光源采用低碳节能的LED(发光二极管)照明技术.制作LED灯的核心材料是().
古希腊美术的基本特点是赞美人性,注重情趣,强调模拟社会。()
最新回复
(
0
)