五分钟C语言数据结构 之 二叉树层次遍历
五分钟C语言实现常见数据结构
今天的内容分享的是二叉树层次遍历
欢迎关注动态规划长文动态规划此一篇就够了 万字总结
二叉树层次遍历
二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历,然后就是层次遍历
将先序遍历、中序遍历和后续遍历进行了简单介绍和C编码之后,进行到了最后的二叉树遍历-层次遍历。层次遍历和之前的方式不一样,就是简单的一层一层的去遍历.
后序遍历过程
借助队列,遍历从根结点开始,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队,直到结点为空
下面借助一幅图来描述其遍历过程:
代码实现
二叉树的层次遍历利用上述的思路进行C语言代码实现:
树形结构按照上述树形结构进行初始化
[*]
[*]
[*]
[*]
[*]
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
//初始化队头和队尾指针
int front = 0, rear = 0;
typedef struct BinTNode{
ElementType data;
struct BinTNode * left;
struct BinTNode * right;
}BinTNode, *BinTree;
BinTNode * CreateBinTree(BinTNode *T) {
T=(BinTNode*)malloc(sizeof(BinTNode));
T->data='A';
T->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->data='B';
T->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->data='C';
T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->data='D';
T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->right->data='E';
T->left->right->left=NULL;
T->left->right->right=NULL;
T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->left->data='H';
T->left->left->left->left=NULL;
T->left->left->left->right=NULL;
T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->right->data='I';
T->left->left->right->left=NULL;
T->left->left->right->right=NULL;
T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
T->right->left->data='F';
T->right->left->left=NULL;
T->right->left->right=NULL;
T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->right->data='G';
T->right->right->left=NULL;
T->right->right->right=NULL;
return T;
}
//入队
void EnQueue(BinTNode ** queue,BinTNode * elem) {
queue = elem;
}
//出队
BinTNode* DeQueue(BinTNode** queue) {
return queue;
}
//输出
void printElement(BinTNode * elem) {
printf("%c ",elem->data);
}
void levelOrderTraverse(BinTNode * tree) {
BinTNode * T;
BinTree queue; // 定义队列
EnQueue(queue, tree); // 初始化,根结点入队
while(front < rear) { // 队列不为空
T = DeQueue(queue); // 结点出队
printElement(T);
// 将出队的结点左右孩子依次入队
if (T->left!= NULL) {
EnQueue(queue, T->left);
}
if (T->right!= NULL) {
EnQueue(queue, T->right);
}
}
}
int main() {
BinTNode * tree;
tree = CreateBinTree(tree);
printf("层次遍历: ");
levelOrderTraverse(tree);
printf("\n");
return 0;
}
执行结果
[*]
层次遍历: A B C D E F G H I
后续会将更多的数据结构用C语言代码实现,欢迎大家关注!
作者:Johngo
图片:凡科快图
互联网广告收入占到互联网收入的80%以上计算广告,一起研究流量变现,欢迎大家的加入
https://blog.51cto.com/u_12099241/4858678
页:
[1]