首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 输出8 6 10 5 7 9 11。
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 输出8 6 10 5 7 9 11。
admin
2019-03-29
117
问题
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。
输出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
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
Directions:Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressy
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
类型声明语句为:INTEGER(2)::I数据输出语句为:PRINT,I变量I中数据输出域宽是____________字符。
改错题【要求】1)打开“T盘”中“P2vbp”文件,按参考界面形式编辑窗体界面,改正程序中的错误后,直接保存所有文件;2)改错时,不得增加或删除语句,但可适当调整语句位置。【题目】本程序的功能是生成由n(n通过InputBox函数输入)个3位升序
路由器的主要作用是()。
对计算机评价的主要性能指标有时钟频率、①、运算精度和内存容量等。对数据库管理系统评价的主要性能指标有②、数据库所允许的索引数量和最大并发事务处理能力等。①处应填入?
阅读以下关于I/O系统处理能力评估的说明,在回答问题1至问题3。拟建设的某事务处理系统数据交换非常频繁。经过初步分析,存储子系统的I/O性能决定了整个系统的响应时间。目前主流磁盘的容量为40GB和80GB两种规格。采用不同规格的磁盘,存储子系统的I
随机试题
领导绩效的基本内容。
酶原激活的生理意义是
国家对药品质量规格及检验方法所做出的技术规定,是药品生产、供应、使用、检验和管理部门共同遵循的法定依据的是有规定的适应症或者功能主治、用法和用量的物质是
【2012年第42题】图3-172示为单跨双层框架,因柱抗弯刚度不同,梁跨中弯矩最小的位置是:
在账务处理系统中进行会计科目设置时,科目代码应()。
计算机资源共享主要包括()。
假定金融机构的法定准备金率为20%,超额准备金率为2%,现金漏损率为3%,则存款乘数为()。
从年龄的角度,更适合接受心理咨询的人群是()。
布鲁纳认为,无论我们选择何种学科,都务必使学生理解该学科的基本结构。依此而建立的课程理论是()。
宏观调控是保证社会再生产协调发展的必要条件,通过宏观调控可以保持经济总量平衡,抑制通货膨胀,促进重大经济结构优化,实现经济稳定增长。下列行为属于宏观调控经济手段的是()。
最新回复
(
0
)