#include<iostream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
#define QUEUE_INIT_SIZE 100
#define QUEUE_INCREMENT 10

typedef struct BiTNode{      //结点结构
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

bool PreOrderTraverse(BiTree &T)  //先序遍历（输出）
{
	if(T){
		cout << setw(3) << T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
	return true;
}

bool InOrderTraverse(BiTree &T)       //中序遍历（输出）
{
	if(T){
		InOrderTraverse(T->lchild);
		cout << setw(3) << T->data;
		InOrderTraverse(T->rchild);
	}
	return true;
}

bool PostOrderTraverse(BiTree &T)    //后序遍历（输出）
{
	if(T){
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout << setw(3) << T->data;
	}
	return true;
}

bool CreateBiTree(BiTree &T)    //构造新树
{
	char ch;
//	cout << "Please enter the chars, 0 to exit: " << endl;
	cin >> ch;
	if(ch == '0') T = 0;
	else{
	if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return false;
		T->data = ch;
		T->lchild = 0;
		T->rchild = 0;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return true;
}

//顺序队列结构的实现

typedef BiTree ElemType;//按实际情况修改		

typedef struct{         //顺序队列结构
	ElemType *base;  
	int front;
	int rear;
	int queuesize;   //队列的当前可使用最大容量
}SqQueue;

bool InitQueue(SqQueue &S)//初始化一个空队列
{
	S.base=(ElemType  *)malloc(QUEUE_INIT_SIZE * sizeof(ElemType));
	if(!S.base) return false;
	S.front=S.rear = 0;
	S.queuesize=QUEUE_INIT_SIZE;
	return true;
}

bool EnQueue(SqQueue &S,ElemType &e) //插入元素e（进队列）
{
	if((S.rear + 1) % S.queuesize == S.front)
	{
		S.base=(ElemType  *)realloc(S.base,(S.queuesize+QUEUE_INCREMENT) * sizeof(ElemType));
		if(!S.base) return false;
		S.queuesize += QUEUE_INCREMENT;

	}
	S.base[S.rear] = e;
	S.rear = (S.rear + 1) % S.queuesize;
	return true;
}

bool DeQueue(SqQueue &S, ElemType &e) //删除元素（出队列）
{
	if(S.front == S.rear) return false;
	e = S.base[S.front];
	S.front = (S.front + 1) % S.queuesize;
	return true;
}

bool QueueEmpty(SqQueue S) //判断队列是否为空
{
	if(S.front == S.rear) 
		return true;
	else 
		return false;
}

int Length(SqQueue S)   //给出队列的长度
{
	return (S.rear - S.front + S.queuesize) % S.queuesize;
}

void levelOutput(BiTree T)
{
	SqQueue S;
	BiTree D;
	InitQueue(S);
	EnQueue(S,T);
	while(!QueueEmpty(S)){
		DeQueue(S, D);
		cout<< setw(3) << D->data;
		if(D->lchild){EnQueue(S,D->lchild);}
		if(D->rchild){EnQueue(S,D->rchild);}
	}
}

bool ChangeBrunch(BiTree &T)  //交换所有左右子树
{
	if(T){
		BiTNode *S;
		S = T->lchild;
		T->lchild = T->rchild;
		T->rchild = S;
		ChangeBrunch(T->lchild);
		ChangeBrunch(T->rchild);
	}
	return true;
}

int main()
{
	BiTree T = 0;
	cout << "请输入字符, 0 为结束: " << endl;
	CreateBiTree(T);          //先序遍历输入一棵二叉树,
	cout << "先序遍立原树： " << endl;
    PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍立原树： " << endl;
    InOrderTraverse(T);
	cout << endl;
	cout << "后序遍立原树： " << endl;
    PostOrderTraverse(T);
	cout << endl;
	cout << "按层输出的树： " << endl;
	levelOutput(T);
	cout << endl;
    ChangeBrunch(T);
	cout << "先序遍立新树： " << endl;
    PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍立新树： " << endl;
    InOrderTraverse(T);
	cout << endl;
	cout << "后序遍立新树： " << endl;
    PostOrderTraverse(T);
	cout << endl;
	cout << "按层输出的新树： " << endl;
	levelOutput(T);
	cout << endl;
}