大家好，又见面了，我是你们的朋友全栈君。
层序遍历图示
实现二叉树的层次遍历，要利用到队列。
基本思想：
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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/143656.html原文链接：https://javaforall.net
