C语言实现二叉树层次遍历介绍

C语言实现二叉树层次遍历介绍

目录

什么是层次遍历?

那我们如何来实现这个算法呢?

主体代码:

总结

什么是层次遍历?

对于一颗二叉树来说,从根节点开始,按从上到下、从左到右的顺序访问每一个结点。

注:每一个结点有且访问一次。

那我们如何来实现这个算法呢?

实现原理:

对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下、从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历。

这里我们需要引用队列来实现。

主体代码: BiTree InitTree()//二叉树的创建 { BiTree T =(BiTree) malloc(sizeof(Tree)); char data; scanf("%c", &data); getchar(); if (data == '#')//如果data为#则该子树为空值 return NULL; else { T->data = data; printf("请输入%c的左子树:\n", data); T->lchild = InitTree(); printf("请输入%c的右子树:\n", data); T->rchild = InitTree(); } return T; } void ShowCengci(BiTree T) { LinkQueue qu; InitQueue(&qu);//初始化队列 enQueue(&qu, T);//根结点入队 while (QueueEmpty(qu))//判断队列中是否为空 { BiTree S = deQueue(&qu);//根节点出队 printf("%c ", S->data); if (S->lchild != NULL)//判断左右子树是否为空,不为空则入队 { enQueue(&qu, S->lchild); } if (S->rchild != NULL) { enQueue(&qu, S->rchild); } }

队列的链式实现:

typedef struct BTree { char data; struct BTree* lchild; struct BTree* rchild; }Tree,*BiTree; typedef struct Queue { BiTree data; struct Queue* next; }Qnode,*Queueptr; typedef struct point { Queueptr front;//头指针 Queueptr rear;//尾指针 }LinkQueue; void InitQueue(LinkQueue* qu) { qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode)); if (qu->front == NULL) return; } void enQueue(LinkQueue* qu, BiTree S) { Queueptr p = (Queueptr)malloc(sizeof(Qnode)); if (p == NULL) { return; } if (S == NULL) return; p->data = S; p->next = NULL; qu->rear->next = p; qu->rear = p; } int QueueEmpty(LinkQueue qu) { if (qu.front != qu.rear) return 1; else return 0; } BiTree deQueue(LinkQueue* qu) { if (qu->front == qu->rear) return; Queueptr p = qu->front->next; BiTree q = p->data; qu->front->next = p->next; if (qu->rear == p) qu->rear = qu->front; free(p); return q; }

通关上述代码可以实现对二叉树的层次遍历。

总结

到此这篇关于C语言实现二叉树层次遍历介绍的文章就介绍到这了,更多相关C语言二叉树内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    区域语言设置|区域语言设置工具

    区域语言设置|区域语言设置工具,,区域语言设置工具你好,大致的方法如下,可以参考:1、按下键盘的windows 图标,再开始菜单中单击“设置”;出现的

    c4d语言设置|c4d汉语设置

    c4d语言设置|c4d汉语设置,,1. c4d汉语设置mac版的C4D是这样的,中文字体是有的,但是是以拼音的形式存在,比如黑体就是ht。中文字体以拼音方式

    电脑宣传语|电脑宣传语言

    电脑宣传语|电脑宣传语言,,1. 电脑宣传语言1.我做好了与你过一辈子的打算,也做好了你随时要走的准备,2.每段青春都会苍老,但我希望记忆里的你

    office语言设置|微软office语言设置

    office语言设置|微软office语言设置,,微软office语言设置一、首先点击桌面左下角“WIN键”。二、弹出选项内点击“所有程序”。三、接着点

    小米设置日语|小米设置日语语言

    小米设置日语|小米设置日语语言,,1. 小米设置日语语言MIUI系统文字目前只支持简体中文、繁体中文、英文、藏文和维吾尔文,不支持日文 2. 小

    易语言开发电脑系统|易语言电脑版

    易语言开发电脑系统|易语言电脑版,,1. 易语言电脑版首先编译——是将程序编译为exe文件,只能在有易语言的机子上运行,独立编译——是将程序