首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
103
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) recursively // the head of BST in initial call /////////////////////////////////////////////////////////////////////// void MirrorRecursively(BSTreeNode *pNode) { if(!pNode) return; // swap the right and left child sub-tree BSTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; // mirror left child sub-tree if not null if(pNode->m_pLeft) MirrorRecursively(pNode->m_pLeft); // mirror right child sub-tree if not null if(pNode->m_pRight) MirrorRecursively(pNode->m_pRight); } 由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下: /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) Iteratively // Input: pTreeHead: the head of BST /////////////////////////////////////////////////////////////////////// void MirrorIteratively(BSTreeNode *pTreeHead) { if(!pTreeHead) return; std::stack
stackTreeNode; stackTreeNode.push(pTreeHead); while(stackTreeNode.size()) { BSTreeNode *pNode = stackTreeNode.top(); stackTreeNode.pop(); // swap the right and left child sub-tree BSTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; // push left child sub-tree into stack if not null if(pNode->m_pLeft) stackTreeNode.push(pNode->m_pLeft); // push right child sub-tree into stack if not null if(pNode->m_pRight) stackTreeNode.push(pNode->m_pRight); } }
解析
尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感觉,就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8,我们交换它的左右子树得到:
我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到:
刚好就是要求的输出。
上面的分析印证了我们的直觉:在遍历二元查找树时每访问到一个结点,交换它的左右子树。这种思路用递归不难实现,将遍历二元查找树的代码稍作修改就可以了。
转载请注明原文地址:https://kaotiyun.com/show/iRmZ777K
0
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Directions:Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressy
ASP.NET与ASP相比,主要有哪些进步?
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
Powerpoint2000中,使用()菜单中的“幻灯片母版”命令,进入幻灯片母版设计窗口,更改幻灯片的母版。A.编辑B.工具C.视图D.格式
如果要将页面上的某个图形设计成页面下载后显示在页面上,当鼠标放在它的上面时,该图形变为另一图形,那么可以通过______方法来设置。A.使用时间线B.“RolloverImage”命令C.将图形插入到表格中D.使用层与行为
在实际应用中,用户通常依靠评价程序来测试系统的性能。以下评价程序中,(16)的评测准确程度最低。事务处理性能委员会(TransactionProcessingPerformanceCouncil,TPC)是制定商务应用基准程序(Benchmark)标
阅读以下关于I/O系统处理能力评估的说明,在回答问题1至问题3。拟建设的某事务处理系统数据交换非常频繁。经过初步分析,存储子系统的I/O性能决定了整个系统的响应时间。目前主流磁盘的容量为40GB和80GB两种规格。采用不同规格的磁盘,存储子系统的I
阅读以下关于税务管理系统方面的叙述,回答问题1和问题2。近年来,我国电子税务工作取得了长足进步,特别是2000年,税务管理信息化工作在国务院领导的直接关心和国家税务总局党组的具体指挥下,以五省四市“金税工程”的顺利开通、平稳运行为标志,取得了突破性
随机试题
患者,女性,45岁,偶然发现左乳房肿块,直径约2cm,质较软、无压痛,与皮肤有少许粘连。左侧腋下可扪及1cm大小肿大的淋巴结。该患者的术后护理措施中不正确的是()。
汉代的以下诉讼制度中,()在一定程度上有利于实现司法公正。
下面关于城市社区管理说法正确的是()。
详细可行性研究阶段的投资估算,其误差率应控制在()以内。
案情简介:京海造纸厂因超标排污影响了周围环境,居民李某等多次找环保局要求解决。1996年2月8日,环保局对造纸厂作出罚款3000元、责令停止排污的处罚决定。此后3个月内,造纸厂既不履行处罚决定,也未向法院起诉。起诉期过后,环保局向人民法院申请强制
我国宏观调控的主要目标是()。
Thegreatestrecentsocialchangeshavebeeninthelivesofwomen.Duringthetwentiethcenturytherehasbeenaremarkablesho
•Readthefaxbelowaboutpeopleexpress.•ChoosethebestwordtofilleachgapfromA,B,CorDontheoppositepage.•For
Lunarsight-seeingtripsandorbitingspacehotelsarewithinreach,moonwalkingastronautEdwin"Buzz"Aldrinsaidlastweek,b
A、Therighthand.B、Thelefthand.C、Bothhands.D、Itdepends.B原文提到,婴儿16周大时,主要使用左手进行触摸,因此B正确。
最新回复
(
0
)