C++实现二叉树层序遍历
2023-06-13 09:11:43 时间
大家好,又见面了,我是你们的朋友全栈君。
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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/143656.html原文链接:https://javaforall.cn
相关文章
- EasyC++06-char类型和输入输出优化
- EasyC++65,运算符重载限制
- 2021年游戏项目的十大编程语言:C++、Java、C#均上榜「建议收藏」
- Python与C/C++的区别(持续更新中……)[通俗易懂]
- C++ – 实现strstr函数
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- 详解二叉树的存储王道版(C++/C)
- c++二叉树的先序,中序,后序遍历_二叉树的构造
- Visual Studio 配置 Halcon C++ 运行环境
- 《安富莱嵌入式周报》第293期:SEGGER开源其C/C++库源码emRun,丰富EMC电磁兼容资,OTA开源组件,2022 Github全球报告,内存安全指南
- C++ 不知树系列之认识二叉树(数组、链表存储的实现)
- c++的链表-C++链表
- c++的链表-链表入门(C++)
- c++基础篇之C++ 模板
- C++派生类的构造函数和析构函数
- C++ set初始化(STL set初始化)详解
- 海量数据处理系列之:用C++实现Bitmap算法
- c++连接mysql数据库的两种方法(ADO连接和mysqlapi连接)
- C++实现位图排序实例