首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
admin
2019-08-01
29
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
试析孙中山新旧三民主义中民族主义的内涵、区别与联系。
试述明代一条鞭法的主要内容和历史意义。
下列法律文件中,规定内阁对君主负责的是()。
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
论述秦国商鞅变法的内容、过程以及重要意义。
苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:()选拓龟板,印成(),这成为甲骨文的第一部著录之作,此后,甲骨学逐渐成为
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是()。
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略,使用2KB的内存空间记录16384个磁盘块的空闲状态。设某单面磁盘旋转速度为6000r/min,每个磁道有100个扇区,相邻磁道间的平均移动时间为1ms。若在某时刻,磁头位于100号磁道处,并沿着磁
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
随机试题
《荷马史诗》提供了丰富的古希腊的历史资料,这反映了艺术的【】
我国公证机构的监督机构有
动物棉籽及棉籽饼粕中毒的临床特征是()。
应急过程中存在的主要问题有()。
根据中国人民保险公司的海洋运输货物的保险条款的规定,货物在运输过程中由于自然灾害和运输工具发生意外事故造成被保险货物的实际全损或推定全损,由于运输工具遭遇搁浅、触礁、沉没、互撞等情况造成保险货物的全部或部分损失,是属于()的保险范围。
空想社会主义的历史观包括历史唯物主义思想萌芽和辩证因素。()
在国有企业改革中对于国有小企业可以采用的方式有( )
判断的敛散性,若收敛是绝对收敛还是条件收敛?
以下使指针指向一个字符串的选项错误的是()。
Modernindustrialsocietygrantslittlestatustooldpeople.Infact,suchasocietyhasasystemofbuilt-inobsolescence.The
最新回复
(
0
)