首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
140
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
程序员面试
相关试题推荐
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
请编程遍历页面上所有TextBox控件并给它赋值为string.Empty?
将一整数逆序后放入一数组中(要求递归实现)
.net中读写数据库需要用到哪些类?他们的作用
存储过程和函数的区别
Powerpoint2000中,使用()菜单中的“幻灯片母版”命令,进入幻灯片母版设计窗口,更改幻灯片的母版。A.编辑B.工具C.视图D.格式
一个软件的架构设计是随着技术的不断进步而不断变化的。以编译器为例,其主流架构经历了管道—过滤器到数据共享为中心的转变过程。以下关于编译器架构的叙述中,错误的是______。
在实际应用中,用户通常依靠评价程序来测试系统的性能。以下评价程序中,(16)的评测准确程度最低。事务处理性能委员会(TransactionProcessingPerformanceCouncil,TPC)是制定商务应用基准程序(Benchmark)标
对计算机评价的主要性能指标有时钟频率、①、运算精度和内存容量等。对数据库管理系统评价的主要性能指标有②、数据库所允许的索引数量和最大并发事务处理能力等。①处应填入?
随机试题
电弧灼眼的原因是什么?怎样防护?
实现分时系统的一种主要方式是()
下列人物中全属于道家的一项是()
A.正链RNA病毒B.负链RNA病毒C.双链RNA病毒D.双链DNA病毒逆转录病毒是
根据《工程咨询成果质量评价办法》,工业建设项目可行性研究报告的质量评价目标包括()。
答辩状、民事调解书、委托书、合同、可行性研究报告、公证书、议案都是司法性文件。()
有的地质学家认为,如果地球的未勘探地区中单位面积的平均石油储藏量能和已勘探地区一样的话,那么,目前关于地下未开采的能源含量的正确估计因此要乘上一万倍。由此可得出结论,全球的石油需求,至少可以在未来五个世纪中得到满足,即使此种需求每年呈加速上升的趋势。为使上
下列关于综合布线的描述中,正确的是
Aestheticthoughtofadistinctivelymodernbentemergedduringthe18thcentury.Thewesternphilosophersandcriticsofthist
Timeisveryimportantinourlives.It【S1】______oureverydaymoments.However,timeneverhadanyimportanceinmylifeuntilI
最新回复
(
0
)