[程序员面试题精选100题]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(两端都可以进出的队列),我们只需要拿过来用就可以了。

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

【代码】

/********************************* * 日期:2013-12-23 * 作者:SJF0115 * 题目: 12.从上往下遍历二元树 * 来源:微软 * 分类:程序员面试题精选100题 **********************************/ #include #include using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(NULL),right(NULL){} }; // 层次遍历 vector LevelOrder(TreeNode* root){ vector vec; if(root == NULL){ return vec; } // 队列 queue queue; queue.push(root); TreeNode *p = NULL; while(!queue.empty()){ // 出队列 p = queue.front(); queue.pop(); // 层次遍历结果 vec.push_back(p->val); // 左子节点不空压入队列中 if(p->left){ queue.push(p->left); } // 右子节点不空压入队列中 if(p->right){ queue.push(p->right); } }//while return vec; } // 二叉查找树插入 void TreeInsert(TreeNode*& root,int val){ // 创建新节点 TreeNode* node = new TreeNode(val); if(root == NULL){ root = node; } else{ TreeNode *pre = NULL; TreeNode *cur = root; // 寻找插入位置 while(cur){ // 父节点 pre = cur; // 沿左子树方向下降 if(val val){ cur = cur->left; } // 沿右子树方向下降 else{ cur = cur->right; } }//while // 插入左子结点处 if(val

val){ pre->left = node; } // 插入右子结点处 else{ pre->right = node; }//if }//if } int main(){ int array[] = {8,6,10,5,7,9,11}; // 创建二叉查找树 TreeNode *root = NULL; for(int i = 0;i vec = LevelOrder(root); for(int i = 0;i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:Java模板引擎 FreeMarker
下一篇:Java集合之LinkedHashSet源码分析
相关文章

程序员的七大武器

教你如何成为一名Java初级程序员

JAVA程序员面试32问,你能回答多少题?

论全世界所有程序员都会犯的错误

论全世界所有程序员都会犯的错误2

用游戏串起程序员的基本功

面向Java程序员的Ajax:构建动态Java程

JAVA程序员必读-编程中一些共同的问题

Java2程序员考试(SCJP) 试题解析

程序员应用EJB 3.0必要的准备

图文推荐

[程序员面试题精选100题]12.从上往下遍历二叉树
适配器模式
[程序员面试题精选100题]12.从上往下遍历二叉树
Handler的介绍和使用
[程序员面试题精选100题]12.从上往下遍历二叉树
struts2上传文件
[程序员面试题精选100题]12.从上往下遍历二叉树
通过JFreeChart的饼状

分类:默认分类 时间:2015-03-07 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 1.447 (s). 10 q(s)