首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
22
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
()用铜制造了人体模型,并统一了人体的穴位。
国际组织的“民主集中制”原则,是在()文献中首次规定的。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
随机试题
下列给定程序中,函数fun的功能是:将s所指字符串中的所有数字字符移到所有非数字字符之后,并保持数字字符串和非数字字符串原有的次序。例如,s所指的字符串为“dei35adh3kjsdf7”,执行后结果为“defadhajsdt3537”。请在程序的下划
在敏捷制造中,最核心的资源是()
A、血液中性粒细胞显著增高B、血液单核细胞显著增高C、血液异型淋巴细胞显著增高D、血液淋巴细胞持续显著增高E、血液嗜碱性粒细胞显著增高中性粒细胞型类白血病可见
某建筑公司制定的生产安全事故现场处置方案,按规定应()至少组织一次演练。
根据我国《合同法》的规定,合同履行中条款空缺首先应当()。
会计软件要具有最大限度地发现错误并提供必要修改手段的功能,即要具有足够的()功能。
弗罗伊德描绘了一场人格的两个不同部分()之间无休止的战争,而这场战争由自我来协调。[2007年真题]
下列哪项属于社会工作者在倡导劳动力市场规范方面的努力?()。
一些乡村在变为城镇的过程中,虽然面貌________,但很多曾经让人留恋的东西却________。人们或多或少有这样的________,快速的、大规模的城镇化会不会使“乡愁”无处安放?填入画横线部分最恰当的一项是:
在数据库系统中,数据模型包括概念模型、逻辑模型和()。
最新回复
(
0
)