?? c實現(xiàn)二叉樹.txt
字號:
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#define max 30
#define queuesize 100
typedef char datatype;
typedef struct node{ /*定義二叉樹鏈表結(jié)點結(jié)構(gòu)*/
datatype data;
struct node *lchild,*rchild;
}BinTNode,*BinTree;
typedef struct
{
int front,rear;
BinTree data[queuesize]; /*定義循環(huán)隊列元素類型為二叉鏈表指針*/
int count;
}cirqueue; /*定義循環(huán)隊列結(jié)構(gòu)*/
void CreateBinTree(BinTree *T) /*先序遞歸建立二叉樹*/
{
char ch;
scanf("\n%c",&ch);
if (ch=='0') *T=NULL; /*讀入0時,將相應(yīng)結(jié)點置空*/
else {*T=(BinTNode*)malloc(sizeof(BinTNode)); /*生成結(jié)點空間*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild); /*構(gòu)造二叉樹的左子樹*/
CreateBinTree(&(*T)->rchild); /*構(gòu)造二叉樹的右子樹*/
}
}
void PreOrder(BinTree t) /*遞歸先序遍歷*/
{
if(t==NULL) return;
printf("%c",t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
void InOrder(BinTree t) /*遞歸中序遍歷*/
{
if(t==NULL) return;
InOrder(t->lchild);
printf("%c",t->data);
InOrder(t->rchild);
}
void PostOrder(BinTree t) /*遞歸后序遍歷*/
{
if(t=NULL) return;
PostOrder(t->lchild);
PostOrder(t->rchild);
printf("%c",t->data);
}
void LevelOrder(BinTree t) /*層次遍歷*/
{ cirqueue *q;
BinTree p;
q=(cirqueue *)malloc(sizeof(cirqueue)); /*申請循環(huán)隊列空間*/
if(!q) return;
q->count=q->rear=q->front=0; /*將循環(huán)隊列初始化為空*/
q->data[q->rear]=t; /*把根結(jié)點入隊列*/
q->count++;
q->rear=(q->rear+1)%queuesize; /*判斷隊列是否為真溢出*/
while(q->count)
{ if(q->data[q->front]) /*如果首元素不為空*/
{ p=q->data[q->front];
printf("%c",p->data); /*打印根結(jié)點元素*/
q->front=(q->front+1)%queuesize;
q->count--; /*隊首元素出列*/
if(q->count==queuesize) /*判斷是否隊滿*/
return;
else
{ q->data[q->rear]=p->lchild; /*左孩子入列*/
q->count++;
q->rear=(q->rear+1)%queuesize;
}
if(q->count==queuesize)
return;
else
{ q->data[q->rear]=p->rchild; /*右孩子入列*/
q->count++;
q->rear=(q->rear+1)%queuesize;
}
}
else /*如果隊首為空指針,將空指針出列*/
{ q->front=(q->front+1)%queuesize;
q->count--;
}
}
}
main()
{ BinTree bt;
CreateBinTree(&bt);
LevelOrder(bt);
getch();
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -