首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
131
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
程序员面试
相关试题推荐
Arogueloosecalledahackercouldtakecontroloftheentiresystembyimplantinghisowninstructionsinthesoftwareandthe
YouhavereceivedaletterfromSophia.Sheexpressedheradmirationformicro-bloggingandwonderedwhetheritcanreplacebook
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:8/\610
如何部署一个ASP.net页面。
什么是ASP.net中的用户控件
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
关系型数据库只能描述()关系。A.网络型B.二维表格C.图D.层次型
改错题【要求】1)打开“T盘”中“P2vbp”文件,按参考界面形式编辑窗体界面,改正程序中的错误后,直接保存所有文件;2)改错时,不得增加或删除语句,但可适当调整语句位置。【题目】本程序的功能是生成由n(n通过InputBox函数输入)个3位升序
在实际应用中,用户通常依靠评价程序来测试系统的性能。以下评价程序中,(16)的评测准确程度最低。事务处理性能委员会(TransactionProcessingPerformanceCouncil,TPC)是制定商务应用基准程序(Benchmark)标
若系统中存在n个等待事务Ti(i=0,1,2,…,n-1),其中:T0正等待被T1锁住的数据项A1,T1正等待被T2锁住的数据项A2,…,Ti正等待被Ti+1锁住的数据项Ai+1,…,Tn-1正等待被T0锁住的数据项A0,则系统处于___________状
随机试题
影响显示器显示清晰程度的一个重要指标是()。
男,10岁,小学生,起病急,畏寒,高热,头痛呕吐已8小时,目前呼之不应。检查:神志不清,面色苍白,四肢厥冷,体温40℃,全身见有广泛斑点、淤斑,有的呈片状,脉细速,血压5.2/0kPa,颈软,脑膜刺激征阴性,血象38×109/L,N0.92,L0.0
患者男,59岁,工人。1年前无明显诱因出现双腕、双手关节和双膝、踝、足、跖趾关节肿痛,伴晨僵;时间约12分钟,疼痛以夜间明显,影响行动。实验室检查:血沉55mm/L,RF(+)。关节X线检查:双手骨质疏松,腕部关节间隙变窄。使用青霉胺治疗,护士应观察哪些
下列关于食品安全管理的法律规定,说法正确的是:
某企业拟采购一批原材料,价值10000元,供应商规定的付款条件如下:(1)立即付款,价格9630元;(2)第20天付款,价格9750元;(3)第40天付款,价格9870元;(4)第60天付款,价格10000元。要求:假设银行短期贷款的利率为23
以下对采购与付款业务流程中付款环节的控制活动以及与相关认定的对应关系的陈述中,不恰当的是()。
在音乐作品中,由原调经过某种中间环节进新调,并在新调上有完全的终止,称之为_________。如果在新调上没有完全的终止,则称之为_________。
2009年H省年末常住人口达到7034.4万人,出生人口90.7万人,出生率为12.93‰;死亡人口45.1万人,死亡率为6.43‰;净增人口45.6万人。2009年城镇居民人均可支配收入达14718.3元。其中,工资性收入9830.6元,增长1
下列关于正当防卫和紧急避险的表述中,正确的是()。
Researchhasshownthatcollegestudentscanlearnasmuch,ormore,frompeersastheydofrominstructorsandtextbooks.When
最新回复
(
0
)