首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
admin
2017-04-28
80
问题
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。
给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转变为递减有序的二叉排序树(前序遍历得递减有序序列),返回根指针;
选项
答案
对于如图3—16a所示的子树,假设根节点P的左子树和右子树都已经经过调整而达到题目的要求,rm结点为右子树前序遍历的最后一个结点,由于P的左子树ltree的元素都小于右子树rtree的任意元素,所以图3—16a右边所示的树是满足题目要求的。类似地,在没有左子树(右子树)的情况下,按方案图3—16b(或图3—16c)调整该树得到的结果是满足要求的。我们可以按递归的方式,对于不同的情况,用图3 —16a、b、c所示三种规则对树进行调整。 [*] 代码如下:Node* reverseTree{Node *p,Node *m){ Node *1, *r, *lm, *rm; if{p—>rchild! =NULL)r=reverseTree (p—>rchild,rm); //递归处理右子树 if(p—>lchild! =NULL)l=reverseTree (p—>lchild,lm); //递归处理左子树 Node *q= (Node *)malloc(sizeof (Node)); //申请并初始化新结点q q—>data=p—>data; q—>lchild=q—>rchild=NULL; m=q; if <r!=NULL) //若递归返回之后右子树不空 { if(1!=NULL) rm—>lchild=1, //若递归返回之后左子树不空 rm— >rchild=q; //结点q作为右孩子 return r; //返回调整后的树 } if(1!=NULL) //若递归返回之后左子树不空 { lm—>lchild=q; //结点q作为左孩子 return 1; //返回调整后的树 } return q;}
解析
转载请注明原文地址:https://kaotiyun.com/show/3PRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在印度独立和巴勒斯坦建国问题上,英国扮演了什么角色?有什么影响?
《关于建国以来党的若干历史问题的决议》
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
下列选项中,对东汉度田问题的描述中,不正确的是()
下面哪项条约没有涉及德国的赔款问题?()
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
在巴黎和会上获利最大的两个国家是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
论述欧洲一体化进程及其影响。
随机试题
判定下列级数的敛散性,若收敛,请指出是条件收敛还是绝对收敛:
要根据树木的用途,采用不同的施肥方案,观叶观形树应多施()。
急性乳腺炎最常见的致病菌是
索赔按照当事人分类不包括()。
下列关于违约金的表述正确的有()。
中央银行的职能包括()。
陈某将装有2万元现金的行李箱寄存在车站寄存处,但在寄存时未告知行李箱内有现金。陈某凭取物单取行李箱发行该行李箱已被人取走,陈某要求寄存处赔偿。根据《合同法》的规定,下列关于寄存处承担赔偿责任的表述中,正确的是()。
消费品所传达的概念远比物体本身重要,它是彰显个人信仰、态度、社会经济地位的名片,这也就是概念消费。普通消费品尽管也能满足人的基本需求,但是它所传达的概念却为普通大众共有,彰显不出消费者的独特性。因此,消费者势必另辟蹊径,寻找一些能标示自己独特性的消费方式。
关于社会发展总体布局问题,十六大提出“三位一体”(经济建设、政治建设、文化建设),十七大提出“四位一体”(经济建设、政治建设、文化建设和社会建设),十八大进一步拓展到“五位一体”(经济建设、政治建设、文化建设、社会建设、生态文明建设)。这一变化包含的哲学道
Brushingyourteethregularlynomatterwhichtoothpasteyouuse,willreduceyourchancesoftoothdecay.Scientistshaveconcl
最新回复
(
0
)