首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。
admin
2019-01-16
24
问题
设排序二叉树中结点的结构由三个域构成:数据域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://jikaoti.com/ti/C3fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
简述格拉古兄弟改革的主要内容和历史意义。
武昌起义所使用的旗帜是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
第三次科技革命对社会经济结构的影响是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
随机试题
莫里哀的《悭吝人》中被认为是财迷、吝啬鬼、守财奴的人物是()
男,20岁。恶心、食欲减退1周,伴发热、尿黄2天。实验室检查:AST358u,ALT564u,TBil59μmol/L,CB28μmol/L,AKP正常。应首先考虑的诊断为
某年3月1日,甲公司就自己不能支付到期债务向人民法院提出破产申请,人民法院于3月10日裁定受理该公司的破产申请,并指定了破产管理人。管理人接管甲公司后,对该公司的财产进行了清理,有关清理情况如下。(1)甲公司资产总额为5600万元(变现价值)。其中全部厂
世界每天石油消费的总量为()万桶。下列说法正确的是()。
①能克服地球引力的火箭是不能“发现”的②“发现”一词与自然界的规律有关,发现规律就像是在海洋中发现过去人们不知道的海岛③而“发明”一词,只与我们如何利用和建设这些海岛有关④火箭只能被构思、设计和制造出来,这是发明⑤而
南京临时政府是一个资产阶级共和国性质的革命政权,这是因为()
表达式(“周”<“刘”)返回的是______。
TheroleofthebodyclockistoFlyinginawestwarddirectionwill
Whatdoesthepassagemainlydiscuss?Accordingtoparagraph3,proponentsofspontaneousgenerationbelievedthatwhichofthe
Bornfromtheaccessibilityofmassairtravel,moderninternationaltourismhasbeenpopularizedas"holiday-making"inregions
最新回复
(
0
)