首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
26
问题
设排序二叉树中结点的结构由三个域构成:数据域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://jikaoti.com/ti/n1fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面有关兵制的内容,与唐玄宗有关的是()
1543年发表解剖学专著《人体结构论》的是()。
中国共产党在下列哪次会议上规定了党的最高纲领和最低纲领?()
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
编写判定给定的二叉树是否是二叉排序树的函数。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
高度为7的AVL树最少有()个结点。
下面关于B-树和B4一树的叙述中,不正确的是()。
随机试题
众所周知,生物多样性是地球生命体系稳态延续的基本前提。但人类社会的活动由于受到价值定位的影响,总会对某些生物物种过分偏爱,而对另一些生物物种漠然视之,甚至对某些物种厌恶有加,因而在地球生命体系中并存的生物物种,在人类社会中总会受到各不相同的待遇。这种不公正
一份填写完整的住院病案首页需要由许多人员共同完成,其中不包括
《建设工程安全生产管理条例》规定,( )和监理工程师应当按照法律、法规和工程建设强制性标准实施监理,并对建设工程安全生产承担监理责任。
提出电信管道、电信杆路、通信铁塔联合建设意向的电信业务经营者召集各参建电信运营商,共同商定(),并签订联合建设协议。
企业在做出促销决策时,首先应当()。
蒙古族禁忌有()。
关于对校法的说法,错误的是()。
不属于民事法律关系的构成要素的是()。
法律思维方式的特征是讲法律、讲证据、讲程序、讲法理。法律上的证据不同于一般的事实,法律上的证据必须具有()
显示器分辩率指的是整屏可显示像素的多少,这与屏幕的尺寸和点距密切相关。例如15英寸的显示器,水平和垂直显示的实际尺寸大约为280mm×210mm,当点距是0.28mm时,其分辨率约为( )。
最新回复
(
0
)