首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二又树树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部删除
admin
2019-08-01
77
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
英国思想家詹姆斯。哈林顿所著《大洋共和国》成书于1656年,书中对托马斯.杰弗逊等美国总统产生重要影响的主张是()
试述中国古代经济重心南移的过程及原因。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
卡德纳斯改革的内容不包括()。
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
抗战时期,国民政府一直没有放弃适当条件的对日妥协,于是,中日之间开始秘密接触,日本称之为()
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
设需在两台计算机间经两个中间节点传送100M字节的文件,假定:(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps;(2)数据传输的差错可以忽略不计;(3)中间节点存储转发时间可忽略不计;
随机试题
社会主义产业结构是指()
1克软脂酸(分子量256)较1克葡萄糖(分子量180)彻底氧化所生成的ATP高多少倍
诊断接触性皮炎最常做的皮肤试验是
健脾丸的功用是枳实消痞丸的功用是
下列车船,自《车船税法》实施之日起5年内免征车船税的有()。(2013年)
明茨伯格认为在构成具体的结构构型时,除了构建模块,还包括(),
下列常识中,正确的有()。
设φ1(x),φ2(x),φ3(x)为二阶非齐次线性方程y"+a1(x)y’+a2(x)y=f(x)的三个线性无关解,则该方程的通解为().
UNIX操作系统一直是最普遍使用的网络操作系统之一,下列说法不正确的是
【S1】【S2】
最新回复
(
0
)