首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
68
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
1543年发表解剖学专著《人体结构论》的是()。
()用铜制造了人体模型,并统一了人体的穴位。
下列各组古代民族,其语言都属于印欧语系的是()。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
下面关于B-树和B4一树的叙述中,不正确的是()。
随机试题
下列一、二级多层公共建筑位于袋形走道尽端的疏散门至最近安全出口撤离,控制严格的是()。
假设投资900万元创业,除预期每年净利为100万元外,10年后该投资可回收本金800万元,年折现率10%,该创业投资______,其净现值为______万元。( )(不考虑税负)
甲企业股东赠予本公司一部分优良资产,合同、协议约定作资本金(包括资本公积)投入,且在会计上已做实际接受投资处理的,则下列说法正确的有()。
()是指商业银行根据约定条件和实际投资收益情况向投资者支付收益,但不保证投资者本金安全、也不承诺收益水平的理财计划类型。
商业汇票的付款人为()。
我国的丹霞风光,南北均有分布,以下属于丹霞风光的是()
在Windows98操作系统启动时,引导的过程按顺序排列应该是( )。 ①装入实模式的设备驱动程序 ②装入操作系统 ③装入并初始化静态vxd ④执行BIOS程序
用OutlookExpress编辑电子邮件。收信地址:mail4test@163.com主题:Linux操作系统介绍将TestIe.txt作为附件粘贴到信件中。信件正文如下:您好!Linux是一款免费的操作系统,用户可
Tocallsomeonebird-brainedinEnglishmeansyouthinkthatpersonissillyorstupid.Butwillthisdescriptionsoondisappear
【S1】【S3】
最新回复
(
0
)