首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 输出8 6 10 5 7 9 11。
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 输出8 6 10 5 7 9 11。
admin
2019-03-29
116
问题
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。
输出8 6 10 5 7 9 11。
选项
答案
#include
#include
using namespace std; struct BTreeNode // a node in the binary tree { int m_nValue; // value of node BTreeNode *m_pLeft; // left child of node BTreeNode *m_pRight; // right child of node }; /////////////////////////////////////////////////////////////////////// // Print a binary tree from top level to bottom level // Input: pTreeRoot - the root of binary tree /////////////////////////////////////////////////////////////////////// void PrintFromTopToBottom(BTreeNode *pTreeRoot) { if(!pTreeRoot) return; // get a empty queue deque
dequeTreeNode; // insert the root at the tail of queue dequeTreeNode.push_back(pTreeRoot); while(dequeTreeNode.size()) { // get a node from the head of queue BTreeNode *pNode = dequeTreeNode.front(); dequeTreeNode.pop_front(); // print the node cout << pNode->m_nValue << ’ ’; // print its left child sub-tree if it has if(pNode->m_pLeft) dequeTreeNode.push_back(pNode->m_pLeft); // print its right child sub-tree if it has if(pNode->m_pRight) dequeTreeNode.push_back(pNode->m_pRight); } }
解析
这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树,只不过不是我们熟悉的前序、中序或者后序遍历。
我们从树的根结点开始分析。自然先应该打印根结点8,同时为了下次能够打印8的两个子结点,我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6 和10了。按照从左往右的要求,我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中,此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器,此时又比5和7先取出,就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。
既然已经确定数据容器是一个队列,现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个,因为STL已经为我们实现了一个很好的deque(两端都可以进出的队列),我们只需要拿过来用就可以了。
我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解,将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。
转载请注明原文地址:https://kaotiyun.com/show/YRmZ777K
0
程序员面试
相关试题推荐
AWelcomeE-mail欢迎邮件Someinternationalstudentsarecomingtoyouruniversity.Writethemane-mailinthenameoftheStudent
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
ASP.NET能在那些系统中运行?
Powerpoint2000中,使用()菜单中的“幻灯片母版”命令,进入幻灯片母版设计窗口,更改幻灯片的母版。A.编辑B.工具C.视图D.格式
若程序内已定义了一个结构型数据:TYPERECORDCHARACTER(len=30)::name,addressINTEGER::Phone_numberENDTYPERECORD则以下类型为RECORD的数组说明语句中正确的是__
路由器的主要作用是()。
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
阅读以下关于I/O系统处理能力评估的说明,在回答问题1至问题3。拟建设的某事务处理系统数据交换非常频繁。经过初步分析,存储子系统的I/O性能决定了整个系统的响应时间。目前主流磁盘的容量为40GB和80GB两种规格。采用不同规格的磁盘,存储子系统的I
随机试题
根据公司法律制度的规定,下列有关公司成立日期的表述中,正确的是()。
关于胰头十二指肠切除术描述正确的是【】
德国的法兰克福是西欧人口最稠密的地区之一。
A、侵袭性腹泻B、分泌性腹泻C、果酱样大便D、嗜酸性粒细胞减少E、嗜酸性粒细胞增加阿米巴痢疾:()
带下的辨证,哪项是错误的
《药品包装、标签规范细则》要求,包装标签内容中用[接种对象]代替[适应证]的药品为()
白喉、百口咳、破伤风混合疫苗初种时需
信息管理所包含的内容除了信息收集,信息加工、信息传输及信息贮存外,还包括()内容。
施工单位在项目开工前必须编制分工计划,逐级向下进行施工组织设计交底,同时进行对有关部门和专业人员的横向交底,并有相应的()。
甲有限公司(以下简称“甲公司”)2×17年、2×18年发生的有关交易或事项如下:(1)2×17年3月1日,甲公司与乙公司签订一项销售合同。合同约定,甲公司应分别于2×18年11月30日和2×19年10月31日向乙公司销售A产品和B产品。合同约定的对价包括
最新回复
(
0
)