二叉树层次遍历流程图（什么是树的层次遍历 要求通俗易懂）

本文目录

• 什么是树的层次遍历 要求通俗易懂
• 已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEICF,请给出其层次遍历序列.
• 用汇编实现二叉树的先序，中序，后序遍历
• 已知二叉树的先序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，画出二叉树
• 建立二叉树，层序、先序遍历
• 建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数

什么是树的层次遍历 要求通俗易懂

二叉树的层次遍历是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。

其思想为：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

1、访问该元素所指向的节点。

2、若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。

扩展资料

由于遍历中所使用的数据结构是一个队列而不是栈，因此写一个按层遍历的递归程序很困难。如下程序用来对二叉树进行逐层遍历，它采用了队列数据结构。队列中的元素指向二叉树节点。当然，也可以采用公式化队列。

程序中，仅当树非空时，才进入w h i l e循环。首先访问根节点，然后把其子节点加到队列中。当队列添加操作失败时，由Add引发NoMem异常，由于没有捕获该异常，因此当异常发生时函数将退出。在把t的子节点加入队列后，要从队列中删除t元素。

已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEICF,请给出其层次遍历序列.

根据先序遍历和中序遍历，我们可以将这颗二叉树画出来，如下图。

所以，根据图片，得出层次遍历序列为：ABCDEFGHI。

用汇编实现二叉树的先序，中序，后序遍历

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==’ ’) T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout《《"malloc fail!";
T-》data=ch;
CreateBiTree(T-》lchild);
CreateBiTree(T-》rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout《《T-》data《《’ ’;
PreOrderTraverse(T-》lchild);
PreOrderTraverse(T-》rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T-》lchild);
cout《《T-》data《《’ ’;
InOrderTraverse(T-》rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T-》lchild);
PostOrderTraverse(T-》rchild);
cout《《T-》data《《’ ’;
}
}
void LevelOrderTraverse(BiTree T){//层序遍历
BiTree Q;
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q; //队头元素出队
front=(front+1)%MaxLength;
cout《《p-》data《《’ ’;
if(p-》lchild){ //左孩子不为空，入队
Q=p-》lchild;
rear=(rear+1)%MaxLength;
}
if(p-》rchild){ //右孩子不为空，入队
Q=p-》rchild;
rear=(rear+1)%MaxLength;
}
}
}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack,p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top》0)
{ while(p!=NULL)
{
cout《《p-》data;
stack=p;
top++;
p=p-》lchild;
}
if (top》0)
{ top--; p=stack; p=p-》rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack,p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top》0)
{ while(p!=NULL)
{
stack=p;
top++;
p=p-》lchild;
}
if (top》0)
{ top--; p=stack;cout《《p-》data; p=p-》rchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s,x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s.ptr = p;
s.tag = 1; //标记为左子树
top++;
p=p-》lchild;
}
while (top》0 && s.tag==2)
{
x = s;
p = x.ptr;
cout《《p-》data; //tag为R，表示右子树访问完毕，故访问根结点
}
if (top》0)
{
s.tag =2; //遍历右子树
p=s.ptr-》rchild;
}
}while (top》0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T-》lchild);
int h3=BTDepth(T-》rchild);
if(h1》h3) return h1+1;
else return h3+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T-》lchild&&!T-》rchild) return 1;
else return(Leaf(T-》lchild)+Leaf(T-》rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T-》lchild)+NodeCount(T-》rchild)+1;
}
void main(){
BiTree T;
T=NULL;
int select;
//cout《《"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"《《endl;
// CreateBiTree(T);
while(1){
cout《《"\n\n请选择要执行的操作:\n";
cout《《"1.创建二叉树\n";
cout《《"2.二叉树的递归遍历算法（前、中、后）\n";
cout《《"3.二叉树的层次遍历算法\n";
cout《《"4.求二叉树的深度\n";
cout《《"5.求二叉树的叶子结点\n";
cout《《"6.求二叉树的结点总数\n";
cout《《"7.二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout《《"0.退出\n";
cin》》select;
switch(select){
case 0:return;
case 1:
cout《《"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"《《endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout《《"未建立树，请先建树！";
else{
cout《《"\n先序遍历:\n";
PreOrderTraverse(T);
cout《《"\n中序遍历:\n";
InOrderTraverse(T);
cout《《"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout《《"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout《《"二叉树的深度为:\n";
cout《《BTDepth(T);
break;
case 5:
cout《《"\n叶子节点数:\n";
cout《《Leaf(T);
break;
case 6:
cout《《"总节点数:\n";
cout《《NodeCount(T);
break;
case 7:
if(!T) cout《《"未建立树，请先建树！";
else{
cout《《"\n先序遍历:\n";
NRPreOrder(T);
cout《《"\n中序遍历:\n";
NRInOrder(T);
cout《《"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout《《"请确认选择项:\n";
}//end switch
}//end while
}

已知二叉树的先序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，画出二叉树

二叉树根节点为A，A的左节点为B，B的右节点为D，A的右节点为C，C的左节点为E，后序遍历序列为DBECA。

画法：根E，E左A右F，A右B，B右D，D左C，F右H，H左G右I，I右K，K左J

先看先序，其第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

扩展资料：

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

建立二叉树，层序、先序遍历

#include 《iostream》
#include "sq_Queue.h"
#define M 1000
using namespace std;
template《class T》
struct Btnode
{T d;
Btnode *lchild;
Btnode *rchild;
};
template《class T》
class Binary_Tree
{private:
Btnode《T》 *BT;
public:
Binary_Tree(){BT=NULL;return;}
void creat_Binary_Tree(T);
void pretrav_Binary_Tree();
void level( );
}；
template《class T》
void Binary_Tree《T》::creat_Binary_Tree(T end)
{
Btnode《T》 *p;
T x;
cin》》x;
if(x==end)
return; p=new Btnode《T》;
p-》d=x;
p-》lchild=NULL;
p-》rchild=NULL;
BT=p;
creat(p,1,end);
creat(p,2,end);
return;
}
template《class T》
static creat(Btnode《T》 *p,int k,T end)
{
Btnode《T》 *q;
T x;
cin》》x;
if(x!=end)
{
q=new Btnode《T》; q-》d=x;
q-》lchild=NULL;
q-》rchild=NULL;
if(k==1) p-》lchild=q; if(k==2) p-》rchild=q; creat(q,1,end); creat(q,2,end); }
return 0;
}
//————————————前序遍历二叉链表——————————————
template《class T》
void Binary_Tree《T》::pretrav_Binary_Tree( )
{
Btnode《T》 *p;
p=BT;
pretrav(p); cout《《endl;
return;
}
template《class T》
static pretrav(Btnode《T》 *p)
{
if(p!=NULL)
{
cout《《p-》d《《" "; pretrav(p-》lchild); pretrav(p-》rchild); }
return 0;
}
//————————————按层次遍历二叉链表——————————————
template《class T》
void Binary_Tree《T》::level( )
{
Btnode《T》 *k;
sq_Queue《Btnode《T》*》q(M);
if(BT!=NULL)
q.ins_sq_Queue(BT);
while(q.flag_sq_Queue( ))
{
k=q.del_sq_Queue( );
cout《《k-》d《《endl;
if(k-》lchild!=NULL) q.ins_sq_Queue(k-》lchild);
if(k-》rchild!=NULL) q.ins_sq_Queue(k-》rchild);
}
return;
}
int main( )
{
Binary_Tree《int》b; cout《《"输入各结点值(-1为结束符值):"《《endl;
b.creat_Binary_Tree(-1); cout《《"前序序列:"《《endl;
b.pretrav_Binary_Tree( );
cout《《"按层次输出二叉链表中所有结点值:"《《endl;
b.level( );
再建立一个用户自定义文件sq_Queue,把下面的考进去
#include 《iostream》
using namespace std;
//定义循环队列类
template《class T》 //模板声明，数据元素虚拟类型为T
class sq_Queue
{private: //数据成员
int mm; //存储空间容量
int front; //排头指针
int rear; //队尾指针
int s; //标志
T *q; //循环队列存储空间首地址
public: //成员函数
sq_Queue(int); //构造函数，建立空循环队列
void prt_sq_Queue(); //输出排头与队尾指针以及队中元素
int flag_sq_Queue(); //检测循环队列的状态
void ins_sq_Queue(T); //入队
T del_sq_Queue(); //退队
};
//建立容量为mm的空循环队列
template《class T》
sq_Queue《T》::sq_Queue(int m)
{mm=m; //存储空间容量
q=new T; //动态申请存储空间
front=mm;
rear=mm;
s=0;
return;
}
//输出排头与队尾指针以及队中元素
template《class T》
void sq_Queue《T》::prt_sq_Queue()
{int i;
cout《《"front="《《front《《endl;
cout《《"rear="《《rear《《endl;
if(s==0){cout《《"队列空！"《《endl;
return;
}
i=front;
do{i=i+1;
if(i==mm+1)i=1;
cout《《q《《endl;
}while(i!=rear);
return;
}
//检测循环队列的状态
template《class T》
int sq_Queue《T》::flag_sq_Queue()
{if((s==1)&&(rear==front))return(-1); //存储空间已满，返回-1
if(s==0)return(0); //循环队列为空，返回0
return(1); //正常返回1
}
//入队
template《class T》
void sq_Queue《T》::ins_sq_Queue(T x)
{if((s==1)&&(rear==front)) //存储空间已满，上溢错误
{cout《《"Queue_overflow!"《《endl;
return;
}
rear=rear+1; //队尾指针进一
if(rear==mm+1)rear=1;
q=x; //新元素入队
s=1; //入队后队列非空
return;
}
//退队
template《class T》
T sq_Queue《T》::del_sq_Queue()
{T y;
if(s==0) //队列为空，下溢错误
{cout《《"Queue_underflow!"《《endl;
return(0);
}
front=front+1; //排头指针进一
if(front==mm+1)front=1;
y=q; //将退队元素赋值给变量
if(front==rear)s=0;
return(y); //返回退队元素
}

建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数

以下是程序代码，里面还包括求树的深度和叶子，已经运行通过了。
#include《stdio.h》
#include《stdlib.h》
#include《string.h》
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode; //自定义二叉树的结点类型
typedef BTNode *BTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNUm为结点数，leaf为叶子数
BTree CreatBTree(void)
{BTree T;
char ch;
if((ch=getchar())==’#’)
return(NULL); //读入#，返回空指针
else{
T=(BTNode *)malloc(sizeof(BTNode));//生成结点
T-》data=ch;
T-》lchild=CreatBTree();//构造左子树
T-》rchild=CreatBTree();//构造右子树
return(T);
}
}
void Preorder(BTree T) //先序遍历
{
if(T){
printf("%c",T-》data);//访问结点
Preorder(T-》lchild);//先序遍历左子树
Preorder(T-》rchild);//先序遍历右子树
}
}
void Inorder(BTree T)//中序遍历
{
if(T)
{
Inorder(T-》lchild);//中序遍历左子树
printf("%c",T-》data);//访问结点
Inorder(T-》rchild);//中序遍历右字树
}
}
void Postorder(BTree T)//后序遍历
{
if(T)
{
Postorder(T-》lchild);
Postorder(T-》rchild);
printf("%c",T-》data);
}
}
int TreeDepth(BTree T)//后序遍历求二叉树的深度，结点数和叶子数
{
int hl,hr,max;
if(T)
{
hl=TreeDepth(T-》lchild);//求左深度
hr=TreeDepth(T-》rchild);//求右深度
max=hl》hr?hl:hr;//取左右深度的最大值
NodeNum=NodeNum+1;//求结点数
if(hl==0&&hr==0)
leaf=leaf+1;
return(max+1);
}
else return(0);
}
void Levelorder(BTree T)//层次遍历二叉树
{
int front=0,rear=1;
BTNode *cq,*p;//定义结点的指针数组cq
cq=T;//根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq;//出队
printf("%c",p-》data);//出队，输出结点的值
if(p-》lchild!=NULL)
{rear=(rear+1)%NodeNum;
cq=p-》rchild;//右子树入队
}
}
}
void main()
{
BTree root;
int i,depth;
printf("\n");
printf("创建二叉树，请输入完全二叉树的先序序列，用#代表虚结点:");
root=CreatBTree();//返回根结点
do{
printf("********************SELECT********************\n");
printf("\t1:先序遍历\n");
printf("\t2:中序遍历\n");
printf("\t3:后序遍历\n");
printf("\t4:深度、结点数、叶子数\n");
printf("\t5:层次遍历\n");
printf("备注：选择层次遍历之前，需要先选择4，求出该树的结点数。");
printf("\t0:Exit\n");
printf("\t*********************************************\n");
scanf("%d",&i);//输入菜单序号
switch(i)
{
case 1:printf("先序遍历结果为:");
Preorder(root);
break;
case 2:printf("中序遍历结果为:");
Inorder(root);
break;
case 3:printf("后序遍历结果为:");
Postorder(root);
break;
case 4:depth=TreeDepth(root);
printf("深度=%d 结点数=%d",depth,NodeNum);
printf("叶子数=%d",leaf);
break;
case 5:printf("层次遍历为:");
Levelorder(root);
break;
default:exit(1);
}
printf("\n");
}
while(i!=0);
}