C++数据结构--按层次遍历二叉树

比眉伴天荒 2021-11-26 23:54 333阅读 0赞

**1.按层次遍历二叉树图解  
![20130801081554703][]  
  
  
  
  
  
  
  
  
示例所用到的二叉树：  
![20130801081617921][]  
  
  
实现代码：  
  
  
\#include<iostream>  
\#include<queue>  
using namespace std;**

**template<typename T>**

**//节点类**

**class node  
\{  
public:  
T val; //节点值  
 node<T>\* left; //左节点   
 node<T>\* right; //右节点  
  
 node():val(T()),left(nullptr),right(nullptr)\{\}  
 node(T v, node<T>\* l=nullptr, node<T>\* r=nullptr):val(v),left(l),right(r)\{\}  
\};  
  
  
  
  
  
  
node<char>\* createBTree()  //构建一棵示例二叉树   
 \{   
node<char>\* d=new node<char>('D');  
node<char>\* e=new node<char>('E');  
node<char>\* b=new node<char>('B',nullptr,d);  
node<char>\* c=new node<char>('C',e,nullptr);  
node<char>\* a=new node<char>('A',b,c);  
  
 \}  
  
 void levelOrderTraver(node<char>\* root)  
 \{   
 queue<node<char>\*> que;  
 node<char> \*tem; //保存队列岀队时的临时变量   
 if(root) //当头节点不为空时  
\{   
  
 que.push(root);  
 while(!que.empty())  
 \{   
tem=que.front(); //取队首元素   
que.pop(); //岀队   
cout<<tem->val<<ends;  
if(tem->left)  //左子树非空时入队   
\{   
que.push(tem->left);  
\}  
  
if(tem->right) //右子树非空时入队   
\{   
que.push(tem->right);  
\}  
 \}  
  
  
\}   
 \}  
  
  
int main()  
\{   
 node<char>\* root=createBTree();  
 cout<<"levelOrderTraver :" ;  
 levelOrderTraver(root);  
 cout<<endl;  
  
  
return 0;  
\}  
  
  
output:  
levelOrderTraver :A B C D E**

**解析：**

**首先根节点入队**

**![20130801081854000][]  
  
![20130801081922359][]**

[20130801081554703]: /images/20211126/05061ab622754c979b52a97891c0f06d.png
[20130801081617921]: /images/20211126/4111cb72ae414beaadc77f9d4e1bf531.png
[20130801081854000]: /images/20211126/4cb02ddd33da42159dbb100070db29ea.png
[20130801081922359]: /images/20211126/583ac452ccc04996be05722a2b816208.png