#include<iostream>
//#include<malloc.h> //c malloc和free,C++ new和delete
using namespace std;
//二叉链表方式，最常用
#define MAXSIZE 100
typedef char ElementType;
struct BTNode{
ElementType data;
BTNode *lchild;
BTNode *rchild;
};
//先序创建二叉树
BTNode * CreateTree(){
BTNode * T=new BTNode;//(BTNode *)malloc(sizeof(BTNode))
char ch;cin>>ch;//输入
if(ch=='#'){
return NULL;
}else{
T->data=ch;
T->lchild=CreateTree();
T->rchild=CreateTree();
}
return T;
}
//先序遍历
void PreOrder(BTNode * T){
//这步判断一定要有，处理建树时的return NULL
if(T){
cout<<T->data;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BTNode * T){
//这步判断一定要有，处理建树时的return NULL
if(T){
InOrder(T->lchild);
cout<<T->data;
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BTNode * T){
//这步判断一定要有，处理建树时的return NULL
if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data;
}
}
//层次遍历,采用顺序循环队列
void LevelOrder(BTNode * T){
//这步判断一定要有，处理建树时的return NULL
if(T){
BTNode * queue[MAXSIZE], * p; //BTNode类型指针数组和BTNode类型指针变量
int front,rear;
front=rear=0;
//若初始 front=rear=0;入队：指针+1--元素入队，出队：指针+1--出队, 栈空条件：front==rear,栈满条件：(rear+1)%MAXSIZE==front
//根节点入队，
rear=(rear+1)%MAXSIZE;
queue[rear]=T;
while(front!=rear){
//出队
front=(front+1)%MAXSIZE;
p=queue[front];
//输出
cout<<p->data;
//左右孩子入队
if(p->lchild){
rear=(rear+1)%MAXSIZE;
queue[rear]=p->lchild;
}
if(p->rchild){
rear=(rear+1)%MAXSIZE;
queue[rear]=p->rchild;
}
}
}
}
int main(){
//freopen("input.txt","r",stdin);//ABD###CE##F##
BTNode * T;
T=CreateTree();
cout<<"先序遍历结果："; PreOrder(T); cout<<endl;
cout<<"中序遍历结果："; InOrder(T); cout<<endl;
cout<<"后序遍历结果："; PostOrder(T); cout<<endl;
cout<<"层次遍历结果："; LevelOrder(T); cout<<endl;
return 0;
}
关于先序建树
