//二叉树基本操作
#include<iostream>
#include <iomanip>
using namespace std;

int i=-1;//用于记录二叉树元素的层次(按树状打印输出)
int j=-1;//用于记录二叉树元素的层次(按凹入表示输出)
int k=0,sum=0;//用于记录二叉树元素的层次(返回T的深度)
int g=0;//用于记录叶子数
typedef struct BiNode{				//二叉链表定义
	char data;
	struct BiNode *lchild, *rchild,*change;//定义一个交换树
}BiTNode, *BiTree;

//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if (ch == '#')  T = NULL;			//递归结束，建空树
	else{
		T = new BiTNode;
		T->data = ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								//else
}									//CreateBiTree

void InOrderTraverse(BiTree T){
	//中序遍历二叉树T的递归算法
	if (T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}
//*****************************请学生把下面函数参数及实现等补充修改完整****************************************

void PreOrderTraverse(BiTree T){
	//先序遍历二叉树T的递归算法
	if (T)
	{
		cout<< T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
void PostOrderTraverse(BiTree T){
	//后序遍历二叉树T的递归算法
	if (T)
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout << T->data;
	}
}
void GYBTraverse(BiTree T)
{//将二叉树以广义表形式输出
	if (T)
	{
		cout<< T->data;
		if(T->lchild!=NULL||T->rchild!=NULL)cout<< '(';
		GYBTraverse(T->lchild);
		if (T->rchild != NULL)cout << ',';
		GYBTraverse(T->rchild);
		if (T->lchild != NULL||T->rchild != NULL)cout << ')';
	}
}
void SX_Traverse(BiTree T)
{//按树状打印输出二叉树的元素,m 表示结点所在层次,初次调用时 m=0    
	if (T)
	{
		i++;
		SX_Traverse(T->rchild);
		cout<<setw(4*i)<<T->data<<endl;
		SX_Traverse(T->lchild);
		i--;
	}	
}
void OR_Traverse(BiTree T)
{//将二叉树以凹入表示形式输出
	if (T)
	{
		j++;
		cout<<setw(4*j)<<T->data<<endl;
		if(!T->lchild&&T->rchild)cout<<setw(4*(j+1))<<"#"<<endl;
		OR_Traverse(T->lchild);
		OR_Traverse(T->rchild);
		if(T->lchild&&!T->rchild)cout<<setw(4*(j+1))<<"#"<<endl;
		j--;
	}
}
int count_n0(BiTree T)
{//计算叶子数
	if (T)
	{
		
		count_n0(T->lchild);
		count_n0(T->rchild);
		if(!T->lchild&&!T->rchild)g++;
	}
	return g;
}
int BiTreeDepth(BiTree T)
{ // 初始条件：二叉树T存在。操作结果：返回T的深度
	if (T)
	{
		k++;
		BiTreeDepth(T->rchild);
		if(k>=sum)sum=k;//用于记录二叉树深度
		BiTreeDepth(T->lchild);
		k--;
	}
	return sum;
}
void ChangeLR(BiTree T)
{//交换左右子树

	if (T)
	{
		ChangeLR(T->lchild);
		ChangeLR(T->rchild);
		T->change=T->lchild;
		T->lchild=T->rchild;
		T->rchild=T->change;
	}
}

void main(){
	BiTree tree;
	cout << "请输入建立二叉链表的序列：\n";
	CreateBiTree(tree);
	cout << "中序遍历的结果为：\n";
	InOrderTraverse(tree);
	cout << endl;
	//*********************以下内容请学生补充完整**************************************
	cout << "先序遍历的结果为：\n";
	PreOrderTraverse(tree);
	cout << endl;

	cout << "后序遍历的结果为：\n";
	PostOrderTraverse(tree);
	cout << endl;

	cout << "将二叉树以广义表形式输出：\n";
	GYBTraverse(tree);
	cout << endl;

	cout << "按树状打印输出二叉树的元素：\n";
	SX_Traverse(tree);
	cout << endl;

	cout << "将二叉树以凹入表示形式输出：\n";
	OR_Traverse(tree);
	cout << endl;

	printf("树的叶子数=%d。\n", count_n0(tree));
	printf("树的深度=%d。\n", BiTreeDepth(tree));

	ChangeLR(tree);//交换左右子树

	cout << "交换二叉树每个结点的左孩子和右孩子：\n";
	cout << "将二叉树以广义表形式输出：\n";
	GYBTraverse(tree);
	cout << endl;

	system("pause");
}