#include <stdio.h>
#include <stdlib.h>
#include<iostream.h>
#define maxnode 100
#define NULL 0
typedef char DataType; /*設(shè)數(shù)據(jù)域類型為字符型*/
typedef struct node{
DataType data;
struct node *lchild,*rchild; /*左右鏈域為指向結(jié)點結(jié)構(gòu)的指針類型*/
}bintnode; /*結(jié)點類型*/
typedef bintnode *bintree; /*指向二叉樹結(jié)點的指針類型*/
void createbintree(bintree *T); /*構(gòu)造二叉鏈表*/
void Preorder(bintree T); /*先序*/
void inorderout(bintree T); /*中序*/
void Postorder(bintree T); /*后序*/
void LevelOrder(bintree T); /*按層次遍歷二叉樹T*/

/*以加入結(jié)點的先序序列輸入，構(gòu)造二叉鏈表*/
void createbintree(bintree *T)
{
char ch;
scanf("\n%c",&ch);
if(ch=='0')*T=NULL;
else
{
*T=(bintnode*)malloc(sizeof(bintnode));
(*T)->data=ch;
createbintree(&(*T)->lchild);
createbintree(&(*T)->rchild);
}

}

/*先序遍歷二叉樹T*/
void Preorder(bintree T)
{
if (T)
{
cout<<T->data; /*訪問結(jié)點數(shù)據(jù)*/
Preorder(T->lchild); /*先序遍歷二叉樹T的左子樹*/
Preorder(T->rchild); /*先序遍歷二叉樹T的右子樹*/
}
}

/*中序遍歷二叉樹T*/
void inorderout(bintree T)
{
if(T)
{
inorderout(T->lchild); /*中序遍歷二叉樹T的左子樹*/
cout<<T->data; /*訪問結(jié)點數(shù)據(jù)*/
inorderout(T->rchild); /*中序遍歷二叉樹T的右子樹*/
}
}

/*后序遍歷二叉樹T*/
void Postorder(bintree T)
{
if (T)
{
Postorder(T->lchild); /*后序遍歷二叉樹T的左子樹*/
Postorder(T->rchild); /*后序遍歷二叉樹T的右子樹*/
cout<<T->data; /*訪問結(jié)點數(shù)據(jù)*/
}
}

void LevelOrder(bintree bt)
{
bintree queue[maxnode];
int front,rear;
if (bt==0)return;
front=-1; /*隊列初始化*/
rear=0;
queue[rear]=bt; /*根結(jié)點入隊*/
while(front!=rear)
{
front++;
cout<<queue[front]->data; /*訪問隊首結(jié)點的數(shù)據(jù)域*/
if(queue[front]->lchild!=NULL) /*將隊首結(jié)點的左孩子結(jié)點入隊列*/
{
rear++;
queue[rear]=queue[front]->lchild;
}//if
if(queue[front]->rchild!=NULL) /*將隊首結(jié)點的右孩子結(jié)點入隊列*/
{
rear++;
queue[rear]=queue[front]->rchild;
}//if
}//while
}//LevelOrder

void main()
{
bintree T;
char a,b;
cout<<"歡迎進入二叉樹基本操作測試程序，請選擇："<<endl;
a='y';
while(a=='y' || a=='Y')
{
cout<<"1-------------------------二叉樹建立"<<endl;
cout<<"2-------------------------先序遍歷!"<<endl;
cout<<"3-------------------------中序遍歷!"<<endl;
cout<<"4-------------------------后序遍歷!"<<endl;
cout<<"5-------------------------層次遍歷!"<<endl;
cout<<"6-------------------------退出!"<<endl;
cin>>b;
switch(b)
{
case '1': cout<<"請按帶空指針的二叉樹先序輸入建立二叉樹存儲的結(jié)點序列:"<<endl;
createbintree(&T);cout<<endl;break;
case '2': cout<<"該二叉樹的先根序遍歷序列為:"<<endl;
Preorder(T);cout<<endl;break;
case '3':cout<<"該二叉樹的中根遍歷序列為:"<<endl;
inorderout(T);cout<<endl;break;
case '4':cout<<"該二叉樹的后根遍歷序列為:"<<endl;
Postorder(T);cout<<endl;break;
case '5':cout<<"該二叉樹的層次遍歷序列為:"<<endl;
LevelOrder(T);cout<<endl;break;
case '6':a='n';break;
default:a='n';
}//switch
}//while
}//main