问题：
输入：ABC##DE#G##F### ，其中#代表空格
输出：先序遍历的序列和中序遍历的序列和后序遍历的序列
分析：
以上的图是根据题目得出的二叉树
按照分析：
得出的先序:ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层次遍历：ABCDEFG
二叉树存储，使用链表更加方便，因此使用链表存储二叉树节点：
定义节点：
typedef struct tree{
char data;
struct tree *lchild;
struct tree *rchild;
};
创建节点：
void create_tree(tree *&t){
char ch=getchar();
if(ch=='#'){
t=NULL;
}else{
t=new tree;
t->data=ch;
create_tree(t->lchild);
create_tree(t->rchild);
}
}
先序遍历：
void pre_order(tree *&t){
if(t){
cout<<t->data<<" ";
pre_order(t->lchild);
pre_order(t->rchild);
}
}
中序遍历：
void zhong_order(tree *t){
if(t){
zhong_order(t->lchild);
cout<<t->data<<" ";
zhong_order(t->rchild);
}
}
后序遍历：
void hou_order(tree *t){
if(t){
hou_order(t->lchild);
hou_order(t->rchild);
cout<<t->data<<" ";
}
}
层次遍历：
void ceng_order(tree *&t){
//使用队，来存储tree结点，先存储根结点，然后循环，队不为空，每次出队，得到队首元素，然后判断这个队首元素的左右节点是否为null，不为null存队
Init_queue();
push_queue(t);
while(!empty_queue()){
tree *t1=pop_queue();
cout<<t1->data<<" ";
if(t1->lchild){
push_queue(t1->lchild);
}
if(t1->rchild){
push_queue(t1->rchild);
}
}
}
层次遍历使用队列来存储，但是由于是自定义的结构体，所以需要自定义队列(1，顺序队列)
(2，链队列)
下面的代码中都有，如果想测试顺序队列，把链队列的注释掉，把顺序队列的打开，其他都不需要变，我的命名都一样
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct tree{
char data;
struct tree *lchild;
struct tree *rchild;
};
//typedef struct queue{ //顺序队
// struct tree *t[100];
// int front;
// int rear;
//}Queue;
//Queue q;
////初始化队
//void Init_queue(){
// q.front=0;
// q.rear=0;
//}
////进队
//void push_queue(tree *&t){
// q.t[++q.rear]=t;
//}
////是否为空
//bool empty_queue(){
// if(q.front==q.rear){
// return true;
// }else{
// return false;
// }
//}
//出队
//tree* pop_queue(){
// return q.t[++q.front];
//}
typedef struct sNode{ //定义链表节点
struct tree *t;
struct sNode *next;
};
typedef struct link_queue{ //定义链表结构
sNode *front;
sNode *rear;
int len;
};
link_queue *l=new link_queue;
void Init_queue(){
sNode *s=new sNode;
s->next=NULL;
l->front=s;
l->rear=s;
l->len=0;
}
//进队
void push_queue(tree *&t){
sNode *s=new sNode;
s->t=t;
s->next=NULL;
l->rear->next=s;
l->rear=s;
l->len++;
}
//判断是否为空
bool empty_queue(){
if(l->front==l->rear){
return true;
}else{
return false;
}
}
//出队
tree* pop_queue(){
tree *t=l->front->next->t;
sNode *s=l->front;
l->front=s->next;
if(l->front==l->rear){ //头结点
l->front=l->rear;
}
delete s;
l->len--;
return t;
}
void create_tree(tree *&t){
char ch=getchar();
if(ch=='#'){
t=NULL;
}else{
t=new tree;
t->data=ch;
create_tree(t->lchild);
create_tree(t->rchild);
}
}
void pre_order(tree *&t){
if(t){
cout<<t->data<<" ";
pre_order(t->lchild);
pre_order(t->rchild);
}
}
void zhong_order(tree *t){
if(t){
zhong_order(t->lchild);
cout<<t->data<<" ";
zhong_order(t->rchild);
}
}
void hou_order(tree *t){
if(t){
hou_order(t->lchild);
hou_order(t->rchild);
cout<<t->data<<" ";
}
}
void ceng_order(tree *&t){
//使用队，来存储tree结点，先存储根结点，然后循环，队不为空，每次出队，得到队首元素，然后判断这个队首元素的左右节点是否为null，不为null存队
Init_queue();
push_queue(t);
while(!empty_queue()){
tree *t1=pop_queue();
cout<<t1->data<<" ";
if(t1->lchild){
push_queue(t1->lchild);
}
if(t1->rchild){
push_queue(t1->rchild);
}
}
}
int main()
{
tree *t;
//创建一颗二叉树
create_tree(t);
//先序遍历
pre_order(t);
cout<<endl;
//中序
zhong_order(t);
cout<<endl;
//后序
hou_order(t);
cout<<endl;
//层次
ceng_order(t);
return 0;
}
结果截图：
