[转]http://zhedahht.blog.163.com/blog/static/2541117420072199173643/
题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。
例如输入
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 // 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<BTreeNode *> 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);
}
}
分享到:
相关推荐
二叉树的层次遍历,是指从二叉树0层的根结点开始,按从上至下,从左至右的顺序访问二叉树中的每次结点。 与二叉树的先序、中序、后序三种遍历方法,层次遍历方法更符合自然习惯。在层次遍历过程中,对某一层的结点...
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5...
(1)编写 AVL树判别程序,并判别一个二元...二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8。 (2)实现 AVL树的 ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树转变为 AVL树的操作。
建立二元树在内存的双链表示算法,并实现先根、中根、后根以及层序遍历算法
问题描述:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入: 8 / / 6 10 / / / / 5 7 9 11 输出 8 6 10 5 7 9 11 定义二元树(其实是二元搜索树,但并不遍历...
假设自上而下按层次,自左至右输入每个结点的一个三元组(N, P, L/R)。其中N为本结点的元素,P为其父结点,L指示N为P 的左孩子,R...试写一个建立二元树在内存的双链表示算法,并实现先根、中根、后根以及层序遍历算法。
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
这是去年做的一份课程设计,用c++,visual studio6.0做的,希望对大家有用处
编写环境 VS2008 支持插入,旋转,平衡等功能。
图的遍历#include #include #define max 100 //定义节点最大个数 int tag[100]; typedef char datatype; /*----------------定义边信息--------------*/ typedef struct node { int adress; // 记录节点位子 ...
迭代过程中记录 (node = 当前节点, cnt = 当前节点遍历过的子节点数量) 二元组,每次取出栈顶元素,如果当前节点是首次出队(当前遍历过的子节点数量为
先将故障树转化成二元决策图,然后通过遍历二元决策图直接获取割集。在转化的过程中,基本事件的排序对二元决策图的规模和计算速度有着直接的影响。寻找基本事件的最优排序是该方法的重点。该文提出的三条排序法则,...
的右孩子 试写一个建立二元树在内存的双链表示算法 并实现先根 中根 后 根以及层序遍历算法 ">假设自上而下按层次 自左至右输入每个结点的一个三元组 N P L R 其 中N 为本结点的元素 P 为其父结点 L 指示N 为P 的左...
输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印。 输入样例: 8 / / 6 10 / / / / 5 7 9 11 输出样例: 代码如下:8 6 10 5 7 9 11 思路分析: 把一颗二叉树抽象成三个节点...
1.简述如何用两个栈模拟一个队列的入队和出队操作.(6 分) 2. 对于图 G5 所示的树:(7 分) 1.设二元树采用左右链存储,写出后序遍历该二元树的非递归
为提高矿井提升机盘式制动系统的可靠性与准确分析系统故障的原因,以TE161型液压站为研究对象,构建动态故障树模型,引入深度优先最左遍历方法,模块化处理动态故障树,建立了静态子树和动态子树,基于二元决策图、...
带有AVL的数据科学三
// 遍历二元查找树中序 void ergodicBSTree(BSTreeNode * pCurrent) { if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { ergodicBSTree(pCurrent->m_pLeft); } // 节点接到链表尾部 ...