首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
admin
2019-08-01
37
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
公元843年,查理曼的三个孙子签订《凡尔登条约》三分查理曼帝国,奠定的三个国家的形是()。①德意志②法兰西③西班牙④意大利
对阿拉伯半岛的统一起了促进作用的宗教是()。
科学社会主义产生的直接思想来源是()。
毛泽东参与重庆谈判的主要目的是()。
论述科举制度的演变及其历史作用。
新中国院系调整主要是学习()。
周王室的两大官僚系统是()。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:金文是指()
在网络中计算机接收的信号是()。
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是()。
随机试题
建设项目的环境影响登记表填报内容包括()
“桃李不言,下自成蹊”,这句话所体现的德育方法是()
(1)______________时左上腹横行带状压痛伴肌紧张;(2)______________时左上腹横行索条状肿物;(3)______________时左上腹坚硬块状结节感肿物。
男性,50岁。慢性咳嗽15年,糖尿病史2年。咳喘加重1个月,发热1周来诊。检查结果:血气分析pH7.25,PaO240mmHg,PaCO285mmHg,BE一10mmol/L。诊断是
理想的疾病名称应是
关于甲的犯罪行为,下列说法正确的是:银行职员丙的行为构成:
某酒店使用的电梯有13部,其中3部电梯已达到设计使用期限,但在每年设备检测报告项目中,各项指标均合格,运行状态良好,酒店希望继续使用。关于达到设计使用年限的特种设备管理的说法,正确的有()。
某公司拟于2017年用自有资金投资购买一成套设备直接投入生产使用(不考虑建设安装期),用于增加原有产品的生产量。购买该成套设备需一次性投资500万元。经测算,该成套设备使用寿命为5年,税法也允许企业按5年计提折旧。设备投入运营后每年可新增税后利润100万元
下列选项中,包括效率差异成本项目的有()。
计算曲面积分,其中Σ为有向曲面z=x2+y2(0≤x≤1),其法向量与z轴正向的夹角为锐角。
最新回复
(
0
)