二叉树的层次遍历。
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
//树结点的数据类型定义
typedef struct BTnode{
DataType data;
struct BTnode* lchild,*rchild;
}BTree;
//队列的结点数据类型定义
typedef struct node{
BTree * tdata; //存放树结点类型的指针
struct node *next;
}qnode;
//队头指针 和 队尾指针
typedef struct {
qnode *front,*rear;
}linkQueue;
//初始化队列
void Init(linkQueue *q)
{
q->front=q->rear=NULL;
}
//元素入队
void InsertQueue(linkQueue * &q,BTree * e)
{
qnode * node;
node=(qnode*)malloc(sizeof(qnode));
node->tdata=e;
node->next=NULL;
if(NULL==q->front)
{
q->front=q->rear=node;
}
else
{
q->rear->next=node;
q->rear=node;
}
}
//元素出队
BTree * outQueue(linkQueue * &q)
{
BTree * e;
qnode *temp;
if(NULL==q->front)
e=NULL;
else
{
temp=q->front;
e=temp->tdata;
q->front=temp->next;
free(temp);
}
return e;
}
//创建二叉树,以先序的方式输入,如果左孩子或右孩子为空,则输入#
/*
例子 A 输入为:ABD##E##CF###
/ \
B C
/ \ /
D E F
*/
void createBTree(BTree * &t)
{
char c;
c=getchar();
if(c=='#')
t=NULL;
else
{
t=(BTree*)malloc(sizeof(BTree));
t->data=c;
createBTree(t->lchild);//创建左子树
createBTree(t->rchild);//创建右子树
}
}
/*
二叉树的层次遍历算法:
1.队列queue初始化;
2. 将根指针入队;
3. 循环直到队列queue为空
3.1 q=队列queue出队的元素;
3.2 访问结点q的数据域;
3.3 若结点q存在左孩子,则将左孩子入队;
3.4 若结点q存在右孩子,则将右孩子入队;
*/
//二叉树的层次遍历
void hierarchyTtraversal(linkQueue *queue,BTree * root)
{
BTree *q;
InsertQueue(queue,root);
while(NULL!=queue->front)
{
q=outQueue(queue);
printf("%c ",q->data);
if(q->lchild)
InsertQueue(queue,q->lchild);
if(q->rchild)
InsertQueue(queue,q->rchild);
}
}
int main()
{
BTree *root;
linkQueue queue;
Init(&queue);
createBTree(root);
hierarchyTtraversal(&queue,root);
printf("\n");
return 0;
}
分享到:
相关推荐
数据结构课程设计实例二叉树层次遍历 数据结构课程设计实例二叉树层次遍历 数据结构课程设计实例二叉树层次遍历 数据结构课程设计实例二叉树层次遍历 数据结构课程设计实例二叉树层次遍历 数据结构课程设计实例...
实现二叉树的层次遍历实现二叉树的层次遍历实现二叉树的层次遍历实现二叉树的层次遍历
数据结构实验3 二叉树层次遍历 二叉树的层次遍历
主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
这是用c语言编写的二叉树层次遍历程序,使用非递归的方法实现。欢迎使用。
在完全二叉树中,在层次遍历和先根序遍历中,已知某节点在一种遍历中的编号,求该节点在另一种遍历中的编号。 程序描述: q = 1表示已知某节点在先根序遍历中的编号,求的是它在层次遍历中的编号。 q = 2表示已知的...
编写程序,用先序递归遍历法建立二叉树的二叉链表存储结构,然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型建议选用字符类型
二叉树的层次遍历 该程序使用队列实现了二叉树的层次遍历,同时使用了广义表表示法来创建二叉树。程序先创建好一棵二叉树,然后调用 levelOrder 函数即可得到该二叉树的层次遍历结果。
实现树的层次遍历 利用c++代码实现。。。。。。。
层次遍历二叉树
目前二叉树普遍用的层次遍历方式是非递归的堆方式,有些考题考了如何用递归方式层次遍历
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
二叉树的层次遍历 两个类 二叉树基本操作类 派生出的层次遍历类 控制台程序
查找算法,二叉排序树,二叉树层次遍历,二叉树非递归遍历,二叉树的建立,关键字匹配查找等。 如有问题,可随时私信。 初学C语言必须掌握的一些基础知识,包括直接选择排序、直接插入排序、冒泡排序、快速排序。 ...
自己写的相当全的二叉树函数操作集合,包括二叉树的递归遍历和非递归遍历,以及计算二叉树的深度和叶子节点等
①初始化一个辅助队列 ②根结点入队 ③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话) ④重复③直至队列为空 ①初始化一个辅助队列
实现了二叉树的前中后遍历,以及层次遍历,求出了二叉树的深度,叶子个数。 实验报告还包含目录,所有遍历方法的解释,以及结果展示和结论改进
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功