层次遍历c语言

㈠ 已知二叉树的先序遍历序列和中序遍历序列，求层次遍历 跪求大牛！（c语言）

typedefstructTree_node{
intdata;
structTree_node*lchild;
structTree_node*rchild;
}NODE,*LINK;
//按层遍历
voidLevelShow(LINKroot)
{
LINKqueue[N+1],p;
intfront=0,rear=0;//队列首尾指针
袭伍if(root==NULL)
{
printf("树不存在，请创建！
");
return;
}
if(root)//若树存在
{
queue[rear++]=root;//根结点进队
while(front!=rear)
{
拍派或p=queue[front++];//出队
printf("%-2d",p->data);
if(p->lchild)queue[rear++]=p->lchild;//若左子树不为空，羡郑则进队
if(p->rchild)queue[rear++]=p->rchild;//若右子树不为空，则进队
}
}
putchar('
');
return;
}

用队列实现。上面是我以前写的，你改下吧！

㈡ C语言二叉树树的层次遍历，为什么出错呢求大神

程序仔细看了一下。
关键点是在层遍历的处理上，有一点点小问题。
应该是先压入当前树结点的左右子树，再弹出当前结旦宴点。
你却是先弹出了模睁银，那还结点都释放了，那里还有结点的左右子树呢？

修改如下，供参考：

#include <stdio.h>早悔
#include <malloc.h>

/*树结点结构体*/
struct tree{
char data;
struct tree *lchild,*rchild;
};
/*队列*/
struct queue{
struct tree *elem;
struct queue *next;
};
/*队列信息表*/
struct queuenode{
struct queue *front,*rear;
};

/*初始化队列信息表*/
struct queuenode *init(struct queuenode *s){
s=(struct queuenode *)malloc(sizeof(struct queuenode));
s->front=(struct queue*)malloc(sizeof(struct queue));
/*s->rear=(struct queue*)malloc(sizeof(struct queue)); 这个是多余的*/
s->rear=s->front;
s->rear->next=NULL;
return s;
}
/*入队*/
void in_queue(struct queuenode *s,struct tree *ch){
struct queue *p;
p=(struct queue*)malloc(sizeof(struct queue));
p->elem=ch;
p->next=NULL;
s->rear->next=p;
s->rear=p;
}
/*出队*/
void out_queue(struct queuenode *s){
struct queue *p;
if(s->front->next!=NULL){
p=s->front->next;
printf("%2c",p->elem->data);
s->front->next=p->next;
if(s->front->next==NULL)
s->rear=s->front;
free(p);
}
}
/*建立树*/
struct tree *create(struct tree *tree){
char ch;
scanf(" %c",&ch);
if(ch=='#')
tree=NULL;
else{
tree=(struct tree *)malloc(sizeof(struct tree));
tree->data=ch;
tree->lchild=create(tree->lchild);
tree->rchild=create(tree->rchild);
}
return tree;
}
/*层遍历*/
void levelorder(struct tree *tree){
struct queuenode *s;
/*这一段没有用
struct tree *a[100];
int rear=0,front=0;
*/
s=init(s);
if(tree){
in_queue(s,tree); /*先插入一个结点*/
while(s->front->next!=NULL){
if(s->front->next->elem->lchild) /*应先插入当前结点的左右子结点*/
in_queue(s,s->front->next->elem->lchild);
if(s->front->next->elem->rchild)
in_queue(s,s->front->next->elem->rchild);
out_queue(s);/*弹出当前结点*/
}
}
}

void main(){
struct tree *t;
printf("输入节点值(按照先序遍历输入)");
t=create(t);
printf("按层遍历(队列):");
levelorder(t);
}

测试用数据：124##5##36##7##
输出： 1 2 3 4 5 6 7

㈢ 由中序遍历和层次遍历还原二叉树。C语言实现

经测，该代码已经修改正确，只需在void BuildTree(char *level,char *inorder,pBiTree T)这里的最后一个变量T改为引用即可。还有一个地方判断调用右子树的地方的判断条件。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedefstruct_BiTree
{
chardata;
struct_BiTree*lchild;
struct_BiTree*rchild;
}BiNode,*pBiTree;

voidBuildTree(char*level,char*inorder,pBiTree&T)
{
inti;
intlen=strlen(level);//取得层次遍历长度
intpos=0;
if(len==0)
return;
char*p=strchr(inorder,level[0]);
if(p==NULL)//如果为空则抛弃第隐丛一个，跳到下一个；
{
char*L=(char*)malloc(sizeof(char)*len);//开辟数组
strncpy(L,level+1,len-1);//舍弃第一个
L[len-1]=0;
BuildTree(L,inorder,T);//调用建树函数
return;
}
亏碧pos=p-inorder;//得到中序遍历左子树字符串长度
T->data=level[0];//为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0)//左子树的递归调用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char*left_level=(char*)malloc(sizeof(char)*len);
char*left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1);//舍去层次遍历第一个
strncpy(left_inor,inorder,pos);//截取左子树字符销携举串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(pos<strlen(inorder)-1)//右子树的递归调用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char*right_level=(char*)malloc(sizeof(char)*(len));
char*right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}

voidpriOrder(pBiTreeT)
{
if(T!=NULL){
printf("%c",T->data);
priOrder(T->lchild);
priOrder(T->rchild);
}
}

voidpostOrder(pBiTreeT)
{
if(T!=NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c",T->data);
}
}

voidfreeNode(pBiTree&T)
{
if(T!=NULL){
freeNode(T->lchild);
freeNode(T->rchild);
free(T);
}
}

intmain()
{
pBiTreeroot;
charlevel[28],inorder[28];
intn;
scanf("%d",&n);
//fflush(stdin);
getchar();
while(n--){
scanf("%s%s",level,inorder);
root=(pBiTree)malloc(sizeof(BiNode));
BuildTree(level,inorder,root);
priOrder(root);
printf("
");
postOrder(root);
printf("
");
//freeNode(root);
}
return0;
}

㈣ 用c语言编一个算法 按层次遍历二叉树的结点

#include<stdio.h>
#include<malloc.h>
// 定义队列的最大长差乎判度
#define QUEUE_LENGTH 100
//
// 二叉树与双向链表数据结构定义，
//
typedef struct struNode
{
int data;
struct struNode *lchild; //二叉树中的左子树或双向链表中的前向指针
struct struNode*rchild; //二叉树中的右子树或双向链表中的后向指针
}BitNode , *BitNodePtr , DuLNode , *DuLNodePtr;
//
// 生成二叉树
//
BitNodePtr Create_bitree()
{
int m;
BitNodePtr T;
T = NULL;
scanf("%d", &m);
if(m)
{
T = (BitNodePtr)malloc(sizeof(BitNode));
T->data = m;
T->lchild = Create_bitree();
T->rchild = Create_bitree();
}
return T;
}
//
// 层次遍历二叉树
//
void ReadBitTree(BitNodePtr pRoot)
{
BitNodePtr pQueue[QUEUE_LENGTH];
int head = 0 , tail = 1;
pQueue[0] = pRoot;
//结束的条件是head向后移动一个位置后，与tail重合
while (head != tail)
{
printf("%d " , pQueue[head]->data);
//左孩子入队列
if (pQueue[head]->lchild)
{
pQueue[tail] = pQueue[head]->lchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//队列长度太小，退出
printf("虚改Queue overflow!");
return;
}
}
//右孩子入队列
if (pQueue[head]->rchild)
{
pQueue[tail] = pQueue[head]->rchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//队列长度顷清太小，退出
printf("Queue overflow!");
return;
}
}
//队首出队列
head = (head + 1) % QUEUE_LENGTH;
}
printf("\n");
return;
}
void main()
{
BitNodePtr Root;
Root = Create_bitree();
ReadBitTree(Root);
return;
}

㈤ C语言实现左孩子右兄弟树的建立，插入，层次遍历，可以加分

问的有些问题，程序建立的2叉树只能是完全2叉树，其他的树只能手动建立，我这里给你完全2叉树的建立和遍历，完全2叉树是没有插入的，给你函数
#include<stdio.h>
#include<stdlib.h>
typedef struct _node_
{
int data;
struct _node_ *lchild,*rchild;
}bitree;
//递归建立完全2x树，root每次遍历后都会返回上层树的根节点，这肢世点容易理解错，最终返回的root是整个2x树历缺肢的根节点，传参int i 是给2x树赋值：1,2,3,4,5……，int n是想建立的总共节点数。
bitree *CreatBitree(int i,int n)
{
bitree *root = (bitree*)malloc(sizeof(bitree));
root->data = i;

if(i * 2 <= n)
root->lchild = CreatBitree(2 * i,n);
else root->lchild = NULL;
if(i * 2 + 1 <=n)
root ->rchild = CreatBitree (2 * i ＋1，n）；
else root->rchild = NULL;
return root;
}

//遍历
void proorder(bitree* root)
{
if(root == NULL) return;
printf("%d ",root->data);
proorder(root->lchild);
proorder(root->rchild);
}//这是根左右遍历即前序遍历，如果想改成中序或者后序只需要把printf改到lchild后和rchild后即可

写完才发现你要层次遍历啊？！，那个还要引入个队列的建立，需要建队，出队，入队的函数，全写出来很麻烦的，写2x树的都不是初学了，我假设你已经有了队列相关函数，给出函数功能注释，然后直接给你层次遍历的函数吧：
void noorder(bitree *root)
{
sequeue *sq;//用的顺序队列，没有用链式的，要不更麻烦了，sequeue是typedef的队列结构体
sq = CreatEmptySequeue();//建立空队列
EnSequeue(sq,root);//根节点入队
while(!EmptySequeue(sq))//判断队列是否空
{
root = Desequeue;//出列
printf("%d",root->data);

if(root->lchild !=NULL)
EnSequeue(sq,root->lchild);
if(root->rchild != NULL)
EnSequeue(sq ,root->rchild);
}
return;
}
算法描述， 利用队列的先进先出的特性，首先把根节点入队列，然后开始循环，先判断队列是否空，取出队首元素并打印，然后检查出列节点的左节点，有的话入队，没有的话检查右节点，有的话入队，开始下次循环，这时队列里是第二层的左节点和有节点，这次是先打印2层左节点，然后让2层的左孩子节点入队，右孩子入队，然后打印2层右节点，然后2层右节点的左孩子入队，右扮慧孩子入队，队列中现在是第3层节点左边依次向右，依次类推，层次打印2x树

看在我折腾了那么多，时隔这么久才有我给答案，分就别吝啬了哈~~~嘿嘿

㈥ C语言 数据结构 二叉树层次遍历

#include"stdio.h"
#include"stdlib.h"

typedefstructbtnode//二叉链表类型冲世定义
{chardata;
structbtnode*lchild,*rchild;
}bintree,*Bintree;
typedefstructLinkQueueNode//链队列类型定义
{bintree*data;
structLinkQueueNode*next;
}LKQueNode;
typedefstructLKQueue
{LKQueNode*front,*rear;
}LKQue;
voidInitQueue(LKQue*LQ)//初始化队列
{LKQueNode*p;
p=(LKQueNode*)malloc(sizeof(LKQueNode));
LQ->front=p;
LQ->rear=p;
(LQ->front)->next=NULL;
}
intEmptyQueue(LKQue*LQ)//判断队列是否为空
{if(LQ->front==LQ->rear)
return1;
elsereturn0;
}
voidEnQueue(LKQue*LQ,Bintreex)//入队好尺列
{LKQueNode*p;
p=(LKQueNode*)malloc(sizeof(LKQueNode));
p->data=x;
p->next=NULL;
(LQ->rear)->next=p;
LQ->rear=p;
}
intOutQueue(LKQue*LQ)//出队列
{LKQueNode*s;
if(EmptyQueue(LQ))
{exit(0);return0;}
else
{s=(LQ->front)->next;
(LQ->front)->next=s->next;
if(s->next==NULL)
LQ->rear=LQ->front;
free(s);
return1;}
}
BintreeGetHead(LKQue*LQ)//取队列首元素
{LKQueNode*p;bintree*q;//q->data=-1;错误在这里没有分配空间就赋值
if(EmptyQueue(LQ))
returnq;
else{p=LQ->front->next;
returnp->data;
}
}
Bintreeinitiate()//建二叉树
{charch;Bintreet;
ch=getchar();
if(ch=='#')t=NULL;
else
{t=(Bintree)malloc(sizeof(bintree));
t->data=ch;
t->lchild=initiate();
t->rchild=initiate();
}
returnt;
}
voidVisit(Bintreep)//访问节点
{printf("%c",p->data);//输出是char
}
intheight(Bintreet)
{intld,rd;
if(t==NULL)return0;
友判高else
{ld=height(t->lchild);
rd=height(t->rchild);
return1+(ld>rd?ld:rd);
}
}

voidlevelorder(Bintreebt)//层次遍历
{LKQueQ;Bintreep;
InitQueue(&Q);
if(bt!=NULL)
{EnQueue(&Q,bt);
while(!EmptyQueue(&Q))
{p=GetHead(&Q);
OutQueue(&Q);
Visit(p);
if(p->lchild!=NULL)EnQueue(&Q,p->lchild);
if(p->rchild!=NULL)EnQueue(&Q,p->rchild);
}
}
}
voidmain()
{BintreeT;
T=initiate();
printf("%d",height(T));
levelorder(T);
}

㈦ 由中序遍历和层次遍历还原二叉树。C语言实现

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<unistd.h>

#include<sys/types.h>

typedefintdata_t;

typedefstructnode

{

data_tdata;

structnode*lchild,*rchild;

}btree;

btree*create_btree(void);

voidpreorder_btree(btree*bt);

voidinorder_btree(btree*bt);

voidpostorder_btree(btree*bt);

intdepth_btree(btree*bt);

voidfree_btree(btree**bt);

voidexchange_btree(btree*bt);

voidprint_btree(btree*bt);//先序遍历皮梁的非递归算法

intmain(intargc,constchar*argv[])

{

btree*bt=create_btree();

preorder_btree(bt);

printf(" ");

printf("depth=%d ",depth_btree(bt));

exchange_btree(bt);

preorder_btree(bt);

printf(" ");

print_btree(bt);

printf(" ");

free_btree(&bt);

preorder_btree(bt);

printf(" ");

return0;

}

btree*create_btree(void)

{

intn;

scanf("%d",&n);

if(n==0)

{

returnNULL;

}

btree*bt=(btree*)malloc(sizeof(btree));

bt->data=n;

bt->lchild=create_btree();

bt->rchild=create_btree();

returnbt;

}

voidpreorder_btree(btree*bt)

{

if(bt)

{

printf("%d,",bt->data);

preorder_btree(bt->lchild);

preorder_btree(bt->rchild);

}

}

voidinorder_btree(btree*bt)

{

if(bt)

{

inorder_btree(bt->lchild);

printf("%d,",bt->data);

inorder_btree(bt->rchild);

}

}

voidpostorder_btree(btree*bt)

{

if(bt)

{

postorder_btree(bt->lchild);

postorder_btree(bt->rchild);

printf("%d,",bt->data);

}

}

intdepth_btree(btree*bt)

{

if(!bt)

{

return0;

}

intldepth=depth_btree(bt->lchild);

intrdepth=depth_btree(bt->rchild);

returnldepth>rdepth?ldepth+1:rdepth+1;

}

voidfree_btree(btree**bt)

{

if(*bt)

{

free_btree(&(*bt)->lchild);

free_btree(&(*bt)->rchild);

free(*bt);

*bt=NULL;

}

}

voidexchange_btree(btree*bt)

{

if(bt)

{

exchange_btree(bt->lchild);

exchange_btree(bt->rchild);

btree*tmp=bt->lchild;

bt->lchild=bt->rchild;

bt->rchild=tmp;

}

}

voidprint_btree(btree*bt)//先序遍历的非递归算法首冲

{

//创建一个栈

btree*stack[20];

者握歼inttop=0;

if(bt)//根不空，根入栈

{

stack[top]=bt;

top++;

}

while(top)//当栈不空

{

top--;

btree*tmp=stack[top];//出栈，访问

printf("%d,",tmp->data);

if(tmp->rchild)//右子树不空，右子树入栈

{

stack[top]=tmp->rchild;

top++;

}

if(tmp->lchild)//左子树不空，左子树入栈

{

stack[top]=tmp->lchild;

top++;

}

}

}

//

对于层次遍历的实现是用队列，根节点入队列然后根节点出队列的同时左节点右节点入队列，这样依次，出一次队列对应出队列的节点左右节点如队列，没有就不入。

㈧ 二叉树的层次遍历算法，c语言。自己写的不知道为啥运行没有显示。

#include<stdlib.h>

#include<stdio.h>

typedefstructbitreenode

{

intdata;

structbitreenode*lchild,*rchild;

typedefstructnode{

bitreedata1;

structnode*next;

typedefstructqueue{

nodeptrfront;

nodeptrrear;

voidenqueue(queueptrq,bitreex){

nodeptrp=(nodeptr)malloc(sizeof(node));

p->data1=x;

p->next=NULL;

if((q->front==q->rear)&&(q->rear==NULL)) //语法疏漏

q->front=q->rear=p;

else{

q->rear->next=p;

q->rear=p;

}

bitree dequeue(queueptrq){

bitreex;

nodeptrp;

if((q->front==q->rear)&&(q->rear==NULL)) //语法疏漏

return0;

p=q->front;

x=q->front->data1;

q->front=p->next;

if(q->rear==p)

q->front=q->rear=NULL; 咐困慧

free(p);

returnx;

intbuildtree(bitreetree){

inta=1;

queueptrq=(queueptr)malloc(sizeof(queue));

q->front=q->rear=NULL;

bitreetmp,tmp1,tmp2;

tree->data=a++; 衡答

enqueue(q,tree);

while(a<16){ //修改了这个while循环

tmp=dequeue(q);

tmp1=(bitree)malloc(sizeof(bitreenode));

tmp1->data=a++;

tmp1->lchild=NULL;

tmp1->rchild=NULL;

tmp->lchild=tmp1;

enqueue(q,tmp1);

tmp2=(bitree)malloc(sizeof(bitreenode));

tmp2->data=a++;

tmp2->lchild=NULL;

尺凯 tmp2->rchild=NULL;

tmp->rchild=tmp2;

enqueue(q,tmp2);

}

return0;

voidlevelorder(bitreetree){

queueptrq=(queueptr)malloc(sizeof(queue));

q->front=q->rear=NULL;

bitreetmp;

enqueue(q,tree);

while(q->front!=NULL){

tmp=dequeue(q);

printf("%d ",tmp->data);

if(tmp->lchild!=NULL)

enqueue(q,tmp->lchild);

if(tmp->rchild!=NULL)

enqueue(q,tmp->rchild);

}

intmain(){

bitreetree=(bitree)malloc(sizeof(bitreenode));

buildtree(tree);

levelorder(tree);

return0;

}

㈨ C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历。下面有我的建树函数，有注释的。

#include"cstdio"
#include"vector"
#include"cstring"
#include"algorithm"
using namespace std;
const int maxn =30;
struct node{
int data;
node* lchild;
node* rchild;
};
int n;
int in[maxn];
bool vis[maxn]={false};
vector<int> lev;
node* create(vector<int> lev,int inl,int inr){
if(lev.size()==0) return NULL;
if(inl>inr) return NULL;
//printf("00\n");
node* root= new node;
root->data =lev[0];
int k;
for(k=inl;k<=inr;k++){
if(lev[0]==in[k])
break;
}
for(int j=inl;j<=k-1;j++)
vis[in[j]]=true;
vector<int> tempLeft,tempRight;//要函旁埋闭数体内新建
for(int i=1;i<运裂lev.size();i++){
if(vis[lev[i]]==true)
tempLeft.push_back(lev[i]);
else
tempRight.push_back(lev[i]);
}
root->液吵lchild =create(tempLeft,inl,k-1);
root->rchild =create(tempRight,k+1,inr);
return root;
}
void preorder(node* root){
if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
int main(){
scanf("%d",&n);
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
lev.push_back(x);
}
for(int j=0;j<n;j++)
scanf("%d",&in[j]);
node *root =create(lev,0,n-1);
preorder(root);
return 0;
}

㈩ 求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"

#define MAX 100

typedef int Element;

typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;

typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;

Queue Qu;

void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();

void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);

int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}

void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}

void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}