题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入
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 <deque>
-
#include <iostream>
-
using namespace std;
-
-
struct BTreeNode
- {
-
int m_nValue;
-
BTreeNode *m_pLeft;
-
BTreeNode *m_pRight;
- };
-
-
-
-
-
-
void PrintFromTopToBottom(BTreeNode *pTreeRoot)
- {
-
if(!pTreeRoot)
-
return;
-
-
- deque<BTreeNode *> dequeTreeNode;
-
-
- dequeTreeNode.push_back(pTreeRoot);
-
while(dequeTreeNode.size())
- {
-
- BTreeNode *pNode = dequeTreeNode.front();
- dequeTreeNode.pop_front();
-
-
-
cout << pNode->m_nValue << ' ';
-
-
-
if(pNode->m_pLeft)
- dequeTreeNode.push_back(pNode->m_pLeft);
-
-
if(pNode->m_pRight)
- dequeTreeNode.push_back(pNode->m_pRight);
- }
分享到:
相关推荐
《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...
程序员面试题精选100题 本资源是程序员面试题精选100题,涵盖了算法、数据结构、操作系统、计算机网络、数据库等多个领域。今天,我们将深入分析其中的一道题目,即将二元查找树转换成排序的双向链表。 知识点一:...
对于程序员面试,理解并能熟练应用这类问题的解决方案,展示了解数据结构和算法的能力,是评估应聘者编程技能的重要标准。同时,能清晰解释和分析递归过程,也是考察逻辑思维和问题解决能力的关键。
具体来说,文档中详细讨论了一个在程序员面试中常见的算法问题:如何将二元查找树(Binary Search Tree,BST)转换为一个排序的双向链表。这是一个涉及树的遍历、指针操作、递归思维的经典算法问题。下面将详细介绍...
本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...
- 使用中序遍历遍历整个二元查找树,因为中序遍历会按照升序顺序访问节点。 - 每访问一个节点,将其添加到已转换的链表的末尾,同时更新前一个节点的指针,指向当前节点。 - 当遍历完所有节点后,整个树就转换成...
【程序员面试题精选100题【数据结构 /算法】】是针对求职程序员精心挑选的一系列面试题目,涵盖了数据结构和算法两大核心领域。这些题目旨在帮助应聘者提高面试技巧,提升对技术的理解,以便在激烈的就业市场竞争中...
这里我们重点讨论的是如何将一个二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表,这是一个典型的面试题,考察了对数据结构的理解和递归算法的应用。 二元查找树是一种特殊的二叉树,每个节点的值...
在程序员面试中,数据结构和算法是经常被考察的重要领域,尤其是涉及到二元查找树(Binary Search Tree, BST)的问题。本题目的核心是将一个二元查找树转换成一个排序的双向链表,这涉及到对树结构的深入理解和递归...
这个面试题要求在不创建新节点的情况下,将给定的二元查找树转换成一个排序的双向链表。有两种主要方法实现这一转换: - **思路一**: - 递归方法:从根节点开始,首先递归处理左子树,将左子树转换为一个有序...
在程序员面试中,掌握各种算法和数据结构是至关重要的,尤其是对于二元查找树(BST)的处理。本题目的核心是将一棵二元查找树转化为一个排序的双向链表,而无需创建新的节点,仅通过调整节点间的指针实现。这种转换...
在程序员面试中,经常会遇到各种各样的题目,旨在考察候选人的算法理解、问题解决能力以及编程技巧。本题是关于将二元查找树(Binary Search Tree, BST)转换为排序的双向链表(Sorted Doubly Linked List)的问题。...