首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
41
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
YouhavereceivedaletterfromSophia.Sheexpressedheradmirationformicro-bloggingandwonderedwhetheritcanreplacebook
TheMagicofSoundMusicisoneofthemostbeautifulformsofartisticexpressionseverinvented.Inmoviesandplays,musi
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
请编程遍历页面上所有TextBox控件并给它赋值为string.Empty?
如何通过ADO.NET读取数据库中的图片?
ASP.net的身份验证方式有哪些?分别是什么原理?
邮件的删除。
软盘写保护的作用是()。A.防止持签B.防止读盘C.防止显示D.防止写盘
随机试题
下列药物中,属于治疗支气管哮喘患者的β2受体激动剂是
下列对蛛网膜下隙出血患者的处理措施中哪项是错误的()。
患儿,男,2岁。形体极度消瘦,面呈老人貌,皮包骨头,腹凹如舟,精神萎靡,大便溏薄,舌淡苔薄腻,其证候是
以下具有抗癌作用的是()。
甲房地产开发企业(以下简称甲企业)开发建设了某住宅小区,取得商品房预售许可证后开始预售。蒋某于2006年3月1日与甲企业签订了购买该小区16幢602室的商品房买卖合同,单价为6000元/米2,并依照约定向房屋登记机构申请办理了相关登记。合同约定建筑面积为1
高天有限责任公司为增值税一般纳税人,历年适用的所得税税率均为33%。高天公司每年按实现净利润的10%提取法定盈余公积,按实现净利搁的10%提取法定公益金.2003年12月10日,公司董事会决定,从2004年起执行《企业会计制度》,并对一系列会计政策作了如下
如果中学生能够有意识地对自己的学习活动进行检查与分析,就意味着他已经掌握了一些()。
太平天国西征的目的是要()。
Whenwesawhisface,weknew______wasbad.
______investigatestheinterrelationoflanguageandmind.
最新回复
(
0
)