層次遍歷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);
}