二叉树（按层建立二叉树，前中后序以及按层遍历）

.h文件
#define _CRT_SECURE_NO_WARNINGS
#include
#include
struct biTree{
char data;
struct biTree * lchild, * rchild;
};
struct biTree * initBiTree();
struct biTree * createBiTree(struct biTree * bt);
int preOrderTraverse(struct biTree * bt);
int inOrderTraverse(struct biTree * bt);
int postOrderTraverse(struct biTree * bt);
int levelOrderTraverse(struct biTree * bt);
int test();
.c文件
#include "二叉树.h"
#define MAX 100
struct biTree * createBiTree(struct biTree * bt){
int front,rear;
char ch;
struct biTree * p,* Queue[MAX];
frOnt=1,rear=0;
printf("按层输入二叉树，虚结点输入‘#‘(结束符为‘@‘)：\n");
while((ch=getchar())!=‘@‘){
p=NULL;
if(ch!=‘#‘){
p=(struct biTree *)malloc(sizeof(struct biTree));
p->data=ch;
p->lchild=p->rchild=NULL;
}
rear++;
Queue[rear]=p;
if(rear==1){
bt=p;
}
else{
if(p!=NULL&&Queue[front]!=NULL){
if(rear%2==0){
Queue[front]->lchild=p;
}
else{
Queue[front]->rchild=p;
}
}
if(rear%2==1){
front++;
}
}
}
return bt;
}
int preOrderTraverse(struct biTree * bt){
if(bt!=NULL){
printf("%c ",bt->data);
preOrderTraverse(bt->lchild);
preOrderTraverse(bt->rchild);
}
return 0;
}
int inOrderTraverse(struct biTree * bt){
if(bt!=NULL){
inOrderTraverse(bt->lchild);
printf("%c ",bt->data);
inOrderTraverse(bt->rchild);
}
return 0;
}
int postOrderTraverse(struct biTree * bt){
if(bt!=NULL){
postOrderTraverse(bt->lchild);
postOrderTraverse(bt->rchild);
printf("%c ",bt->data);
}
return 0;
}
int levelOrderTraverse(struct biTree * bt){
struct biTree * Queue[MAX],* p;
int front,rear;
frOnt=rear=0;
if(bt!=NULL){
Queue[rear]=bt;
rear++;
while(front!=rear)
{
p=Queue[front];
front++;
printf("%c ",p->data);
if(p->lchild!=NULL){
Queue[rear]=p->lchild;
rear++;
}
if(p->rchild!=NULL){
Queue[rear]=p->rchild;
rear++;
}
}
}
return 0;
}
int test(){
struct biTree * bt;
bt=(struct biTree *)malloc(sizeof(struct biTree));
bt=createBiTree(bt);
preOrderTraverse(bt);
printf("\n");
inOrderTraverse(bt);
printf("\n");
postOrderTraverse(bt);
printf("\n");
levelOrderTraverse(bt);
return 0;
}
int main(){
test();
return 0;
}

二叉树（按层建立二叉树，前中后序以及按层遍历）,布布扣,bubuko.com