首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2019-01-16
61
问题
设排序二叉树中结点的结构由三个域构成:数据域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://www.kaotiyun.com/show/SlRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
唐代在广州设立管理对外商务的是()。
1543年,发表了解剖学专著《人体结构》的是()。
隋唐科举制的进士科最先出现在()。
武昌起义所使用的旗帜是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
下列关于塞尔维乌斯改革的叙述中,不正确的是()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
随机试题
用于血栓栓塞性疾病的药物有:
强心苷治疗心功能不全疗效最好的适应证是
利多卡因不能用于局部麻醉。()
研究房地产项目的市场表现方式,确定房地产项目从产品到商品的过程中的最佳表达方式是()。
下列战争及战争结果对应正确的是()。
电脑出现故障时,判断与处理的原则不包括___________。
在一个Access的表中有字段"书籍名称",要查找包含"计算机"三个字的记录,正确的条件表达式是()。
将高级语言编写的程序翻译成机器语言程序,采用的两种翻译方式是______。
Travelingcanbefunandeasy.Avacationtriptoanothercountryisespecially【21】______whenthetravelingconditionsareg
A、Campjobs.B、Ajobatahotel.C、Ajobintheopenair.D、Cuttinggrass.C细节题。这位男士说喜欢在户外工作,所以应选C。
最新回复
(
0
)