Question

求一个关于二叉树遍历的程序

要求是这样的，先人工输入一个n值，然后生成一个n层的满二叉树，输出。再输入1，2，3，分别代表先序，中序，后序遍历，按输入的方法遍历后输出，谢谢大家！！！！

Answer 1

运行结果：
n = 3

1:先序遍历:
2:中序遍历:
3:后序遍历:
4:层序遍历:
0:退出
选择____1

先序遍历: ABDECFG

1:先序遍历:
2:中序遍历:
3:后序遍历:
4:层序遍历:
0:退出
选择____2

中序遍历: DBEAFCG

1:先序遍历:
2:中序遍历:
3:后序遍历:
4:层序遍历:
0:退出
选择____3

后序遍历: DEBFGCA

1:先序遍历:
2:中序遍历:
3:后序遍历:
4:层序遍历:
0:退出
选择____4

层序遍历: ABCDEFG

1:先序遍历:
2:中序遍历:
3:后序遍历:
4:层序遍历:
0:退出
选择____

#include<iostream.h>
#include<math.h>

struct BiT {
char data;
BiT *lchild, *rchild;
};

BiT* CreateBiTree(int n) {
//构造二叉链表表示的二叉树T
int i, m = pow(2,n)-1;
BiT *c = new BiT[m];
for(i = 0; i < m; i++) {
c[i].data = 'A' + i;
c[i].lchild = &c[2*i+1];
c[i].rchild = &c[2*i+2];
}
for(i = pow(2,n-1)-1; i < m; i++)
c[i].lchild = c[i].rchild = NULL;
return c;
}

void PreOrderTraverse(BiT *T) {
// 先序遍历二叉树T
if (T) {
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

void InOrderTraverse(BiT *T) {
// 中序遍历二叉树T
if (T) {
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}

void PostOrderTraverse(BiT *T) {
// 后序遍历二叉树T
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}

struct Queue {
BiT *P;
Queue *next;
};

struct LinkQueue {
Queue *front; //队头指针
Queue *rear; //队尾指针
};

void InitQueue(LinkQueue *Q, BiT *T) {
Q->front = new Queue;
Q->front->P = T;
Q->rear = new Queue;
Q->front->next = Q->rear;
Q->rear->P = NULL;
}

void EnQueue(LinkQueue *Q, BiT *e) {
if(!e) return;
Q->rear->P = e;
Q->rear->next = new Queue;
Q->rear = Q->rear->next;
Q->rear->P = NULL;
}

void DeQueue(LinkQueue *Q) {
Queue *q = Q->front;
Q->front = Q->front->next;
delete q;
}

void LevelOrderTraverse(BiT *T) {
if(!T) return;
LinkQueue *Q = new LinkQueue;
InitQueue(Q,T);
while(Q->front->P) {
cout<<Q->front->P->data;
EnQueue(Q,Q->front->P->lchild);
EnQueue(Q,Q->front->P->rchild);
DeQueue(Q);
}
}

void main() {
int n;
cout<<" n = ";
cin>>n;
BiT *T = CreateBiTree(n);
do { cout<<"\n 1:先序遍历:"
"\n 2:中序遍历:"
"\n 3:后序遍历:"
"\n 4:层序遍历:"
"\n 0:退出"
"\n 选择____";
cin>>n;
switch(n) {
case 1: cout<<"\n 先序遍历: "; PreOrderTraverse(T); cout<<endl; break;
case 2: cout<<"\n 中序遍历: "; InOrderTraverse(T); cout<<endl; break;
case 3: cout<<"\n 后序遍历: "; PostOrderTraverse(T); cout<<endl; break;
case 4: cout<<"\n 层序遍历: "; LevelOrderTraverse(T); cout<<endl; break;
}
}while(n);
}