层序遍历二叉树算法

① 二叉树的层次遍历算法

二叉树的层次遍历算法有如下三种方法：

给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：

之后大家就可以自己画图了，下面给出程序代码：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最后给出完成代码的测试用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

for (i = 0; ; i++) {

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

② 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法

//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;

void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}

}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;

createBTree(&(*tree)->left);

createBTree(&(*tree)->right);

}
}

void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}

void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}

visitBTree(q);
}
}

③ 二叉树层次遍历算法

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}

void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}

④ 二叉树层次遍历怎么进行

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}

DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！

⑤ 二叉树层次遍历

/**
*层序遍历
*/
voidLevelOrderTraversal(BinTree*BT){
	BinTree*T;
	T=BT;
	if(!T){
		return;
	}
	Queue*Q=InitQueue();	/*生成一个队列*/
	EnQueue(Q,T);		/*根节点入队*/
	while(!IsQueueEmpty(Q)){		/*队列不为空,弹出一个元素*/
		T=DeQueue(Q);
		Visited(T);		/*访问*/
		if(T->Left)		/*左子树不为空入队*/
			EnQueue(Q,T->Left);
		if(T->Right)	/*右子树不为空入队*/
			EnQueue(Q,T->Right);
	}
}

你的代码貌似不对，原因是：你只是把根节点进了队列！看看我写的！

同时你也可以直接用网络搜索“C实现二叉树（模块化集成，遍历的递归与非递归实现）”，这是博客园的一个博文，里面有关二叉树的前中后层遍历的递归与非递归算法，比较全面。

⑥ 层序遍历二叉树

#include<stdio.h>
#include<stdlib.h>
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜单==============");
printf("\n 1.建立二叉树方法 1");
printf("\n 2.建立二叉树方法 2");
printf("\n 3.先序递归遍历二叉树");
printf("\n 4.中序递归遍历二叉树");
printf("\n 5.后序递归遍历二叉树");
printf("\n 6.层次遍历二叉树");
printf("\n 7.计算二叉树的高度");
printf("\n 8.计算二叉树中叶结点个数");
printf("\n 9.交换二叉树的左右子树");
printf("\n 10.打印二叉树");
printf("\n 0.结束程序运行");
printf("\n===============================");
printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",&k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n请输入二叉树各节点的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍历二叉树：");
preorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 4:if(t)
{printf("中序遍历二叉树：");
inorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 5:if(t)
{printf("后序遍历二叉树：");
postorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 6:if(t)
{printf("层次遍历二叉树：");
levorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 7:if(t)
{printf("二叉树的高度为：%d",treedepth(t));
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 8:if(t)
{printf("二叉树的叶子结点数为：%d\n",leafcount(t));
printf("二叉树的叶结点数为：");paintleaf(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 9:if(t)
{printf("二叉树的左右子树：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 10:if(t)
{printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再见! 按回车键，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n请输入二叉树各结点的编号和对应的值(如：1，a):");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n 请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",&e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){

inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level+1;j++)printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);exchange(bt->rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}

⑦ 二叉树的层次遍历

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}

DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！

⑧ 如何用c语言实现层次遍历二叉树

下面是c语言的前序遍历二叉树的算法，在这里假设的节点元素值假设的为字符型，
说明：算法中用到了结构体，也用到了递归的方法，你看看怎么样，祝你好运！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定义链表结构
{
elemtype
data;
//定义节点值
struct
note
*lchild;
//定义左子节点值
struct
note
*rchild;
//定义右节点值
}btree;
preorder(btree
*root)
//前序遍历
{
if(roof!=null)
//如果不是空节点
{
printf("%c\n",root->data);
//输出当前节点
preorder(root->lchild);
//递归前序遍历左子节点
preorder(root->rchild);
//递归前序遍历右子节点
}
return;
//结束
}

⑨ 二叉树的层次遍历以及用层次遍历算法显示所有叶子节点

#include <iostream>
using namespace std;
struct segtree{int a,b;} tree[10001];
void buildtree(int l,int r,int root = 0) //建树 { tree[root].a=l; tree[root].b=r; if (l==r) return; int mid=(l+r)>>1; root<<=1; buildtree(l,mid,root+1); buildtree(l,mid,root+2);}
void dfs(int level,int root = 0){ for (int i=1;i<level;i++) cout<<' '; cout<<"Lv"<<level<<" : ["<<tree[root].a<<","<<tree[root].b<<"]\n"; if (tree[root].a!=tree[root].b) { root<<=1; dfs(level+1,root+1); dfs(level+1,root+2); }}
struct {int root,level;} st[100001];
void bfs(){ int top=1,first=0; st[first].root=0; st[first].level=1; while (first<top) { for (int i=st[first].level;i>1;i--) cout<<' '; cout<<"Lv"<<st[first].level<<" : ["<<tree[st[first].root].a<<","<<tree[st[first].root].b<<"]\n"; if (tree[st[first].root].a!=tree[st[first].root].b) { st[top].root=st[first].root*2+1; st[top++].level=st[first].level+1; st[top].root=st[first].root*2+2; st[top++].level=st[first].level+1; } first++; }}
int main(){ int t,i; cout<<"以[1,9]线段树为例，生成一个二叉树。\n\n"; buildtree(1,9); cout<<"以深度遍历该树（深搜）：\n"; dfs(1); cout<<"以深度遍历该树（宽搜）：\n"; bfs(); system("pause"); return 0;}

⑩ 编写按层次顺序（同一层从左至右）遍历二叉树的算法

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}

void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}
遍历方法从void cengci(bitree *t) 开始的 用队列方法遍历的