// 程序员面试100题(算法)之层次遍历二叉树(用队列实现)
#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;
struct BiTreeNode
{
BiTreeNode *leftNode;
BiTreeNode *rightNode;
int value;
};
BiTreeNode *CreateBiTree(BiTreeNode *&root)
{
int data = 0;
cin >> data;
if(-1 == data)
return NULL;
else
{
root= (BiTreeNode*)malloc(sizeof(BiTreeNode));
if(root)
{
root->value = data;
root->leftNode = NULL;
root->rightNode = NULL;
CreateBiTree(root->leftNode);
CreateBiTree(root->rightNode);
}
else
{
cout << "No space" <<endl;
return NULL;
}
}
return root;
}
void PreTraverseBiTree(BiTreeNode *root)
{
if(root)
{
cout << root->value << "\t";
PreTraverseBiTree(root->leftNode);
PreTraverseBiTree(root->rightNode);
}
}
void LevelTraverse(BiTreeNode *root)
{
deque<BiTreeNode *> dequeTree;
if(NULL == root)
return;
dequeTree.push_back(root);
while(!dequeTree.empty())
{
BiTreeNode *node = dequeTree.front();
cout << node->value << "\t";
dequeTree.pop_front();
if(node->leftNode)
dequeTree.push_back(node->leftNode);
if(node->rightNode)
dequeTree.push_back(node->rightNode);
}
cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
BiTreeNode *root = NULL;
cout << "Please create the tree with preorder(-1 means NULL):" << endl;
CreateBiTree(root);
cout << "The result of preorder traverse is:" << endl;
PreTraverseBiTree(root);
cout << endl;
cout << "The result of level-traverse is:" << endl;
LevelTraverse(root);
return 0;
}
分享到:
相关推荐
2. 二叉树层次遍历.c:演示了如何使用层次遍历算法遍历二叉树,按照从上到下、从左到右的顺序输出节点的值。 3. 二叉树非递归遍历.c:展示了如何使用非递归方式实现二叉树的前序、中序和后序遍历。 4. 二叉树建立....
文档中涵盖了二叉树的基本概念,包括如何在Java中实现二叉树,并介绍了如何使用前序、中序和后序遍历方法来遍历二叉树。此外,文档还包括一个逐步指南,介绍如何在Java中实现二叉树的打印代码,包括详细的代码示例和...
二叉树算法实现,二叉树定义,二叉树实现步骤,使用算法学习人群,简单易懂,更是采用三大语言实现:python实现、Java实现、C语言实现
也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开。 以下直入主题: 定义一颗二叉树,请看官自行想象其形状, class BinNode( ): def __init__( self, val ): ...
通过C语言数据结构二叉树来实现遍历、冒泡排序、快速排序等算法的实现。本设计将主要包括以下内容: ## 一、研究背景 二叉树是一种重要的数据结构,在计算机科学领域中被广泛应用。二叉树不仅是一种数据结构,而且...
* 遍历-层次遍历 * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表...
摘要:面试也是一门学问,在面试之前做好充分的准备则是成功的必须条件,而程序员在代码面试时,常会遇到编写算法的相关问题,比如排序、二叉树遍历等等。 在程序员的职业生涯中,算法亦算是一门基础课程,尤其是在...
一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下,供大家参考。 具体代码如下: class ...
一、基本题 1. 一元多项式的表示和相加(链表、建立、相加、输出) 2.... (2) 前序、中序、层次非递归遍历该二叉树。 (3) 判断该二叉树是否为二叉排序树。 (4) 如果是二叉排序树,进行结点的插入或
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
》主要定位于有一定C/C++语言编程基础、想通过学习算法与数据结构提升编程水平的读者,也可作为具有一定编程经验的程序员以及大中专院校学生学习数据结构和算法的参考书。 第1篇 算法基础篇 1 第1章 算法概述 2 ...
程序员笔试知识点总结整理。包括:常考基础必知必会;二叉树三种遍历的非递归算法;线性表;树与二叉树;图;单源最短路径;等。
请用java写二叉树算法,实现添加数据形成二叉树功能,并以先序的方式打印出来. 43.请写一个java程序实现线程连接池功能? 44.给定一个C语言函数,要求实现在java类中进行调用。 45.如何获得数组的长度? 46....
本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物,也可供自学之用。 目录 出版者的话 译者序 前言 第一部分 基础知识 第1章 引言 1.1 算法 1.2 典型问题——连通性 1.3 合并一...
C语言实现数据结构算法初阶算法:顺序表、单向链表、双向循环链表、栈、队列、二叉树的遍历、创建哈夫曼树、求解哈夫曼编码。
11.3 遍历二叉树 11.3.1 先序遍历 11.3.2 中序遍历 11.3.3 后序遍历 11.3.4 广度优先(按层)遍历 11.4 森林、树和二叉树的转换 11.4.1 森林、树和二叉树的转换 11.4.2 树的链表存储 11.5 哈夫曼树 11.5.1...
二叉树遍历 该模块实现了二叉树的三种遍历方式。用户可以对树的每一个节点输入值构造二叉树。 栈 该模块提供了一个模拟的栈,用户可以点击入栈和出栈,在界面上方观察出入栈的过程,在操作中明白栈——这种运算受限...
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...