求学快递网 软考
发布资讯
您当前的位置:首页 > 软考 > 计算机软件水平考试《程序员》面试题精选题(4)

计算机软件水平考试《程序员》面试题精选题(4)

上传时间: 2017-12-18 11:17:53 来源:用户上传
浏览量:758 评论数:0 举报
导读: 想要第几时间获得软考考试报考信息,想要充分利用各种精华资讯资源备考,想要海量高质量、高含金量的习题练习,关注“求学快递网”公众号,你不能错过的考试利器!

  -从上往下遍历二元树

  题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。

  例如输入

  8

  / \

  6 10

  /\ /\

  5 7 9 11

  输出8 6 10 5 7 9 11。

  分析:这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树,只不过不是我们熟悉的前序、中序或者后序遍历。

  我们从树的根结点开始分析。自然先应该打印根结点8,同时为了下次能够打印8的两个子结点,我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6 和10了。按照从左往右的要求,我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中,此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器,此时又比5和7先取出,就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。

  既然已经确定数据容器是一个队列,现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个,因为STL已经为我们实现了一个很好的deque(两端都可以进出的队列),我们只需要拿过来用就可以了。

  我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解,将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。

  参考代码:

  #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);

  }

  }

赞(32) 不喜欢(0) 收藏
免责声明 : 本站为免费网络服务提供商,为注册用户提供免费信息存储空间服务,网站所有信息均为用户自行发布并由用户承担相应法律责任,本站不对用户发布的信息进行修改及审核,不对发布信息的真实性及合法性负责,如涉及侵权或者信息违法的请你及时与本站联系进行删除以保障你的合法权益。详情可阅读本站免责声明

相关推荐:

发表评论 用户评价仅供其表达个人意见,与本站无关

还可以输入235个字

最热评论

new 最新评论

大家都在看
>
热门课程培训

建议反馈表

非常感谢您给我们提出的问题或建议,我们会尽快处理! ×

反馈类型:

问题描述:

您的联系方式:

客服电话:

×
投诉举报
选择举报类型
×
投诉举报
填写并确认举报信息
为了确保问题能及时得到处理,请务必保证您提交的信息真实有效、清晰完整

*举报理由:

*举报描述:

截图证明:

×
投诉举报
填写并确认举报信息
为了确保问题能及时得到处理,请务必保证您提交的信息真实有效、清晰完整

*举报描述:

*原文链接:

联系方式:

截图证明:

×
投诉举报

当您发现本站有涉及个人的侵权内容时,建议您先尝试与当事人沟通解决问题。 如果您无法联系到当事人,您可通过此渠道提交举报诉求。

根据求学快递网侵权举报规范,您需要向我们提交您的个人信息,其中包括身份证明。如您确认已准备齐全,可点击下方按钮进入诉求提交页。

如果您举报的仅仅是辱骂等不友善内容,无需提交证明资料,可返回上一步点击【包含有害内容>辱骂、歧视、挑衅和诽谤等不友善信息】直接举报。
×
投诉举报

当您发现本站有涉及企业的侵权内容时,建议您先尝试与当事人沟通解决问题。 如果您无法联系到当事人,您可通过此渠道提交举报诉求。

根据求学快递网侵权举报规范,您需要向我们提交您企业和个人的证明材料。如您确认已准备齐全,可点击下方按钮进入诉求提交页。

如果您举报的仅仅是辱骂等不友善内容,无需提交证明资料,可返回上一步点击【包含有害内容>辱骂、歧视、挑衅和诽谤等不友善信息】直接举报。
×
投诉举报
填写并确认举报信息
为了确保问题能及时得到处理,请务必保证您提交的信息真实有效、清晰完整

*举报理由:

举报描述:

截图证明: