`

程序员面试题精选(12)-从上往下遍历二元树

阅读更多

题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入
       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(两端都可以进出的队列),我们只需要拿过来用就可以了。
我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解,将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。
参考代码:

C++代码 复制代码
  1. #include <deque>   
  2. #include <iostream>   
  3. using namespace std;   
  4.   
  5. struct BTreeNode // a node in the binary tree   
  6. {   
  7.       int          m_nValue; // value of node   
  8.        BTreeNode   *m_pLeft;  // left child of node   
  9.        BTreeNode   *m_pRight; // right child of node   
  10. };   
  11.   
  12. ///////////////////////////////////////////////////////////////////////   
  13. // Print a binary tree from top level to bottom level   
  14. // Input: pTreeRoot - the root of binary tree   
  15. ///////////////////////////////////////////////////////////////////////   
  16. void PrintFromTopToBottom(BTreeNode *pTreeRoot)   
  17. {   
  18.       if(!pTreeRoot)   
  19.             return;   
  20.   
  21.       // get a empty queue   
  22.        deque<BTreeNode *> dequeTreeNode;   
  23.   
  24.       // insert the root at the tail of queue   
  25.        dequeTreeNode.push_back(pTreeRoot);   
  26.       while(dequeTreeNode.size())   
  27.        {   
  28.             // get a node from the head of queue   
  29.              BTreeNode *pNode = dequeTreeNode.front();   
  30.              dequeTreeNode.pop_front();   
  31.   
  32.             // print the node   
  33.              cout << pNode->m_nValue << ' ';   
  34.   
  35.             // print its left child sub-tree if it has   
  36.             if(pNode->m_pLeft)   
  37.                    dequeTreeNode.push_back(pNode->m_pLeft);   
  38.             // print its right child sub-tree if it has   
  39.             if(pNode->m_pRight)   
  40.                    dequeTreeNode.push_back(pNode->m_pRight);   
  41.        }   
分享到:
评论

相关推荐

    程序员面试题精选100题-何海涛

    《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...

    程序员面试题精选100题

    程序员面试题精选100题 本资源是程序员面试题精选100题,涵盖了算法、数据结构、操作系统、计算机网络、数据库等多个领域。今天,我们将深入分析其中的一道题目,即将二元查找树转换成排序的双向链表。 知识点一:...

    程序员面试题精选100题.doc

    对于程序员面试,理解并能熟练应用这类问题的解决方案,展示了解数据结构和算法的能力,是评估应聘者编程技能的重要标准。同时,能清晰解释和分析递归过程,也是考察逻辑思维和问题解决能力的关键。

    程序员面试题精选100题(经典!)

    具体来说,文档中详细讨论了一个在程序员面试中常见的算法问题:如何将二元查找树(Binary Search Tree,BST)转换为一个排序的双向链表。这是一个涉及树的遍历、指针操作、递归思维的经典算法问题。下面将详细介绍...

    程序员面试题精选100题.docx

    本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...

    程序员面试题精选100题(自己整理)

    - 使用中序遍历遍历整个二元查找树,因为中序遍历会按照升序顺序访问节点。 - 每访问一个节点,将其添加到已转换的链表的末尾,同时更新前一个节点的指针,指向当前节点。 - 当遍历完所有节点后,整个树就转换成...

    程序员面试题精选100题【数据结构 /算法】

    【程序员面试题精选100题【数据结构 /算法】】是针对求职程序员精心挑选的一系列面试题目,涵盖了数据结构和算法两大核心领域。这些题目旨在帮助应聘者提高面试技巧,提升对技术的理解,以便在激烈的就业市场竞争中...

    程序员面试题精选100题.pdf

    这里我们重点讨论的是如何将一个二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表,这是一个典型的面试题,考察了对数据结构的理解和递归算法的应用。 二元查找树是一种特殊的二叉树,每个节点的值...

    程序员面试题精选63题

    在程序员面试中,数据结构和算法是经常被考察的重要领域,尤其是涉及到二元查找树(Binary Search Tree, BST)的问题。本题目的核心是将一个二元查找树转换成一个排序的双向链表,这涉及到对树结构的深入理解和递归...

    程序员面试题精选100题与解法

    这个面试题要求在不创建新节点的情况下,将给定的二元查找树转换成一个排序的双向链表。有两种主要方法实现这一转换: - **思路一**: - 递归方法:从根节点开始,首先递归处理左子树,将左子树转换为一个有序...

    程序员面试题精选100题目

    在程序员面试中,掌握各种算法和数据结构是至关重要的,尤其是对于二元查找树(BST)的处理。本题目的核心是将一棵二元查找树转化为一个排序的双向链表,而无需创建新的节点,仅通过调整节点间的指针实现。这种转换...

    程序员面试题精选(附答案及分析)

    在程序员面试中,经常会遇到各种各样的题目,旨在考察候选人的算法理解、问题解决能力以及编程技巧。本题是关于将二元查找树(Binary Search Tree, BST)转换为排序的双向链表(Sorted Doubly Linked List)的问题。...

Global site tag (gtag.js) - Google Analytics