首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
32
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
国际组织的“民主集中制”原则,是在()文献中首次规定的。
下面哪项条约没有涉及德国的赔款问题?()
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
关于B一树,下列说法不正确的是()。
设有3阶B一树,如图1-4所示。从(1)得到的B-树上删除66。试画出删除后的B-树。
以下有关m阶B一树的说法中正确的有()。Ⅰ.每个结点至少有两棵非空子树Ⅱ.树中每个结点至多有m-1个关键字Ⅲ.所有叶子在同一层上Ⅳ.当插入一个数据项引起B-树结点分裂后,树长高一层
随机试题
4G的主要特点
A.复方碘溶液B.利舍平C.131I治疗D.甲状腺素片E.丙硫氧嘧啶仅用于手术前准备于甲状腺危象的药物是
以石棉水泥和膨胀水泥封口的接口,要用稀泥糊口作保水养生,气温低于( )时不得施工。
城市维护建设税的计税依据包括()。
某电厂与某水运公司签订一份运输保管合同,合同载明的费用为500000元(运费和保管费未分别记载)。货物运输合同的印花税税率为0.5‰,仓储保管合同的印花税税率为1‰,该项合同双方各应缴纳的印花税税额为()元。
在督查工作中,协助领导搞好预案和各项准备工作,收集各类情况、搞好综合分析研究,提出落实的措施,为修正和完善决策提出意见和建议,这种督查工作方法称为()。
某苗木公司准备出售一批苗木,如果每株以4元出售,可卖出20万株,若苗木单价每提高0.4元,就会少卖10000株。那么,在最佳定价的情况下,该公司最大收入是多少万元?
关于菜单设计,下列叙述中错误的是()。
Whateffectdoesexcessivepositiveionizationhaveonsomepeople?Byobservingthebehaviourofanimals,scientistsmaybeab
Theword"freedom"formanyblackAmericansisinextricablylinkedwiththeword"slavery."Whileithas148years【M1】______si
最新回复
(
0
)