首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 定义二元查找树的结点为: struct BSTreeNode // a node in the bi
admin
2019-03-29
141
问题
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
定义二元查找树的结点为:
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
程序员面试
相关试题推荐
Thecommitteehasanticipatedtheproblemsthat______intheroadconstructionproject.
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
活动目录的作用
数据库的优化设计?
在控制面板中,将鼠标的"右手习惯"改为"左手习惯"。
如果要将页面上的某个图形设计成页面下载后显示在页面上,当鼠标放在它的上面时,该图形变为另一图形,那么可以通过______方法来设置。A.使用时间线B.“RolloverImage”命令C.将图形插入到表格中D.使用层与行为
软盘写保护的作用是()。A.防止持签B.防止读盘C.防止显示D.防止写盘
在使用SELECT-SQL语句进行查询操作时,可以进行集合的并运算,即将多个基本的SELECT-SQL语句运行结果进行合并。这时,需要使用关键词(或称为运算符)________将多个基本的SELECT-SQL语句进行组合。
随机试题
某公司于2007年发行面额为1元的普通股1000万股,每股发行价格为8元,融资费用率为全部发行所得资金的2%,第一年股利率为10%,以后每年递增5%。2008年市场无风险报酬率为10%,市场平均风险股票必要报酬率为13%,该公司普通股β值为1.7。要
溯洄从之,道阻且跻。
[*]
适于采用观察法收集资料的是
工程建设监理招标的宗旨是对监理单位()的选择。
某商业银行在发放贷款时,要求借款人以第三方作为还款保证。若借款人在贷款到期时不能偿还贷款本息,则保证人必须代为清偿。这是风险管理技术和措施的()方法。
根据商标法及相关规定,工商行政管理部门处理侵犯注册商标专用权纠纷,认定侵权行为成立的,可以作出下列哪些决定?
德育过程是培养学生品德的过程,学生的品德包括()。
商鞅变法
Whichofthefollowingcentralbankactionswouldbeappropriatetocombatrapidinflation?
最新回复
(
0
)