首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出~个正整数x。请编写非递归程序,实现将data域的值小于等于x的结点全部
admin
2018-08-12
29
问题
设排序二叉树中结点的结构由三个域构成:数据域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
学硕统考专业
相关试题推荐
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
请根据下面材料,结合相关知识,分析其内容及意义。他命令所有罗马人都进行登记并用银对自己的财产估价,按照习惯宣誓保证所报各项均属真实,全部财产均已按最高价格估价,并陈报父亲系何人,自己的年龄,自己的妻子和子女的名字,每人的籍贯隶属市中哪个部落或乡间
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
关于B一树,下列说法中不正确的是()。
以下有关m阶B一树的说法中正确的有()。Ⅰ.每个结点至少有两棵非空子树Ⅱ.树中每个结点至多有m-1个关键字Ⅲ.所有叶子在同一层上Ⅳ.当插入一个数据项引起B-树结点分裂后,树长高一层
随机试题
下列说法错误的是()。
市场营销是一个系统工程,这个系统包括制约一个企业投入与产出的全部要素。
阅读下面小说片段,回答下列问题:他的苦恼刚淡忘了不久,如今重又出现,更有力地撕扯他的胸膛。姚纳的眼睛不安而又痛苦地打量街道两旁川流不息的人群:在这成千上万的人当中有没有一个人愿意听他倾诉衷曲呢?然而人群奔走不停,谁都没有注意到他,更没有注意到他
A.辛伐他汀B.非诺贝特C.多烯康D.考来烯胺E.阿西莫司
下列除哪项外,均是采录“主诉”所要求的内容
下述情形中,属于三级医疗事故的是造成病员
直接人工的用量标准是()。
【1917年宪法】
Onetypeofpersonthatiscommoninmanycountriesistheonewhoalwaystriestodoaslittleaspossibleandtogetasmuchi
Thestudentsexpectedthere_____morereviewingclassesbeforethefinalexams.
最新回复
(
0
)