C++实现二叉树层序遍历

全栈程序员站长

发布于 2022-08-31 18:17:35

6700

发布于 2022-08-31 18:17:35

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

444

层序遍历图示

实现二叉树的层次遍历，要利用到队列。基本思想： 1.先将根节点放到队列中 2.根节点弹出队列，然后将根节点的左、右儿子入队 3.弹出左儿子，放入左儿子的左右儿子 4.弹出右儿子，放入右儿子的左右儿子 5.重复3、4步

图示过程：所用的二叉树如下

队列的操作：

将根节点弹出，放入左右儿子：

将B节点弹出，放入左右儿子(只有右儿子)：

把D节点弹出，放入左右儿子：

C、E、F都没有儿子节点，所以直接弹出队列即可：

C++代码实现

1.利用前序遍历思想输入二叉树。(前序创建二叉树：创建二叉树) 2.进行层序遍历

#include <iostream>
#include <queue>
#include <malloc.h>

using namespace std;

typedef char DataType;

typedef struct Node *BinTree;
typedef BinTree Link;
typedef struct Node BinTNode;

struct Node{ 
   
	DataType data;
	Link Left,Right;
};

//创建二叉树
void creat_BinTree(BinTree *T){ 
   
	char ch;
	
	scanf("%c",&ch);
	if(ch=='#'){ 
   
		*T=NULL;
	}else{ 
   
		*T=(BinTNode*)malloc(sizeof(BinTNode));
		(*T)->data=ch;
		(*T)->Left=NULL;
		(*T)->Right=NULL;
		
		creat_BinTree(&((*T)->Left));
		creat_BinTree(&((*T)->Right));
	}
	return ;
} 

//层序遍历
void LevelOrder(BinTree BT){ 
   
	queue<BinTNode*> q;
	BinTree T;
	if(!BT)return;
	q.push(BT);
	while(!q.empty()){ 
   
		T=q.front();
		q.pop();
		printf("%c ",T->data);
		if(T->Left)q.push(T->Left);
		if(T->Right)q.push(T->Right);
	}
} 

int main(int argc, char** argv) { 
   
	BinTree Tree;
	creat_BinTree(&Tree);
	
	LevelOrder(Tree);
	
	return 0;
}