数据结构二叉树层次遍历 C语言

心已赠人 2022-04-10 01:47 208阅读 0赞

## C语言 数据结构 二叉树层次遍历 ##

原创作者：**小林**  
\#include<stdio.h>  
\#include<stdlib.h>  
\#define max 100

typedef int ElemType;

typedef struct BiTNode\{  
ElemType data;  
struct BiTNode \*lchild,\*rchild;  
\} BiTNode,\*BinTree;

//建立二叉树

void CreateBinTree(BinTree &T)\{ //按先序次序输入，构造二叉链表表示的二叉树T  
int num;  
scanf("%d",&num);//输入函数。  
if(num==-1)\{  
T=NULL;  
\}//输入\#时为空  
else\{  
T=(BinTree)malloc(sizeof(BiTNode));  
T->data=num;  
CreateBinTree(T->lchild);  
CreateBinTree(T->rchild);  
\}  
\}

// 遍历二叉树  
void LevleOrder(BinTree T)\{ //从第一层开始，从左到右

BinTree Queue\[max\],p; //用一维数组表示队列，front和rear分别表示队首和队尾指针

int front,rear;

front=rear=0;

if (T) //若树非空  
\{

Queue\[rear++\]=T; //根结点入队列

while (front!=rear)\{ // 队列非空  
p=Queue\[front++\]; // 队首元素出队列，并访问这个结点  
printf("%d",p->data);

if (p->lchild!=NULL) Queue\[rear++\]=p->lchild; //左子树非空，入队列  
if (p->rchild!=NULL) Queue\[rear++\]=p->rchild;  
\}  
\}

//按要求输出二叉树

int main() \{

BinTree T;

printf("\\n创建二叉树\\n");  
CreateBinTree (T);  
printf("\\n层次遍历二叉树 并输出遍历结果\\n"); LevleOrder(T);

return 0; \}

例题：  
二叉树的层次遍历  
关于二叉树的遍历方法，除了我们所熟知的先序遍历、中序遍历和后序遍历方法外，还有一种遍历方法，称为层次遍历。所谓层次遍历方法是指从二叉树的根结点开始自上而下，每一层从左到右逐一访问每个结点。例如，若二叉树如下所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NDMxMg_size_16_color_FFFFFF_t_70]

则该二叉树的层次遍历序列为：1 2 3 5 6 7 10 11 13  
假设二叉树采用二叉链表存储结构，其二叉链表的类型定义如下。  
typedef struct bnode\{  
int data; //结点的数据域用大于0的整数表示  
struct bnode \*lchild;  
struct bnode \*rchild;  
\}bnode,\*btree;  
要求：  
首先采用先序遍历的方法来创建一棵二叉树，创建时用-1来表示空树。最后输出所创建二叉树的层次遍历序列。  
例如，如果要创建上图所示的二叉树：  
应输入：  
1 2 -1 5 10 -1 -1 11 -1 -1 3 6 -1 13 -1 -1 7 -1 -1  
则输出：  
1 2 3 5 6 7 10 11 13

运行结果如下：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NDMxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NDMxMg_size_16_color_FFFFFF_t_70]: /images/20220404/e8c2292ff491420f99f86b3430fb7dbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NDMxMg_size_16_color_FFFFFF_t_70 1]: /images/20220404/2c7b132a776543649b17a2ed83bbdce9.png