五分钟C语言数据结构 之 二叉树层次遍历

PHP小丑

五分钟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[rear++] = elem;
}

//出队
BinTNode* DeQueue(BinTNode** queue) {
  return queue[front++];
}

//输出
void printElement(BinTNode * elem) {
  printf("%c ",elem->data);
}

void levelOrderTraverse(BinTNode * tree) {
  BinTNode * T;
  BinTree queue[20];    // 定义队列
  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%以上计算广告，一起研究流量变现，欢迎大家的加入