首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
129
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
YourfriendDavidjustsentyouabookthatyouexpectedasabirthdaypresent.Sendane-mailtohimtoexpressyourappreciati
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
TheMagicofSoundMusicisoneofthemostbeautifulformsofartisticexpressionseverinvented.Inmoviesandplays,musi
ASP.NET能在那些系统中运行?
什么是ASP.net中的用户控件
创建一个新的邮件。
邮件的删除。
关于计算机语言的描述,不正确的是()。A.机器语言的语句全部由0和1组成,指令代码短,执行速度快B.机器语言因为是面向机器的低级语言,所以执行速度慢C.汇编语言已将机器语言符号化,所以它与机器无关D.汇编语言比机器语言执行速度快
随机试题
对于百日咳患儿,抗生素首选
关于水泥混凝土散水、明沟的伸缩缝设置的做法,符合要求的是()。
A、Evolutionofmonarchbutterflies.B、Livinghabitsofmonarchbutterflies.C、Migrationpatternsofmonarchbutterflies.D、Envir
在分析工程项目抗风险能力时,应分析工程项目在不同阶段可能遇到的不确定性因素和随机因素对其经济效果的影响,这些阶段包括工程项目的()。
用友报表系统中,报表公式定义包括()。
“备案号”栏应填()。“征免性质”栏应填()。
甲公司共有三个车间,2007年3月份生产A产品5000件,相关的资料如下: 要求: (1)编制产成品入库的会计分录; (2)采用成本还原的方法确定每件产品中的直接材料费用、直接人工费和制造费用。
在Word中,对于具有多页文字的文档,如何最快地删除全部内容?()
公安政策属于公安对策体系的范畴。()
A、 B、 C、 B
最新回复
(
0
)