首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
112
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
程序员面试
相关试题推荐
TheGreeksassumedthatthestructureoflanguagehadsomeconnectionwiththeprocessofthought,whichtookrootinEuropelon
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
Directions:Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressy
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树转换成双向链表4=6=8=10=12=14=16。
使用.NETPassport向导注册MSN帐户,姓名为李明,邮件的地址为liming@hotmail.com,密码为123456lm。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
软盘写保护的作用是()。A.防止持签B.防止读盘C.防止显示D.防止写盘
【程序说明】使用如下表的数据:SQL语句SELECT部门表.部门号,部门名称,商品号,商品名称,单价;FROM部门表,商品表;WHERE部门表.部门号=商品表.部门号;ORDERBY部门表.部门号DESC,单价
企业战略数据模型可分为两种类型:(35)描述日常事务处理中的数据及其关系;(36)描述企业管理决策者所需信息及其关系。35
随机试题
有以下程序:#include<stdio.h>main(){inta=1,b=0:printf("%d,",b=a+b);printf("%d\n",a=2*b);}程序运行后的输出结果是()。
关于胆汁的生理作用,错误的是()
男。78岁。晨起四肢乏力。2小时前行走中跌倒,不能起立。体检:意识清楚,只能以眼球上下运动示意。双侧周围性面瘫,张口伸舌和吞咽不能,留置鼻饲。四肢肌力0级,腱反射亢进,双侧Babinski征阳性。感觉无异常。脑梗死部位在
A.药品经营企业不得经营B.由国务院药品监督管理部门规定的药品批发企业经营C.由省级药品监督管理部门规定的药品批发企业经营D.应当具有保证供应责任区域内医疗机构所需麻醉药品和第一类精神药品的能力并具有保证麻醉药品和第一类精神药品安全经营的管理制
相对于固定预算法,下列属于弹性预算法特点的有()。
以下属于广告创意策略类型的是()。
Treatacnebreakoutswithahomemadeexfoliatingmask—thispowerfulcocktailofingredientsworkstocalmirritatedskin,aswel
党执政兴国的第一要务是()
在20初出现的资产阶级革命组织中,孙中山领导的中国同盟会是第一个资产阶级政党,这是因为它
CompaniesAreWorkingwithConsumerstoReduceWasteA)Asconsumers,weareverywasteful.Annually,theworldgenerates1.3b
最新回复
(
0
)