//* * * * * * * * * * * * * * * * * * * * * * * *
//数据结构课程实验	实验三 树和二叉树			*
//03计本3班										*
// 樊海军 2B0324151138							*
//* * * * * * * * * * * * * * * * * * * * * * * *

#include <stdio.h>
#include <stdlib.h> 

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int status;

typedef struct BiNode//二叉链表
{
    char Data;
    struct BiNode* lChild;
    struct BiNode* rChild;
}BiNode,*pBiNode;

typedef struct SNode/*链栈的结点类型*/
{
	pBiNode elem; /*栈中的元素是指向二叉链表结点的指针*/
	struct SNode *next;
}SNode;

struct  link  //队列链表
{
	struct   BiNode *p;
	struct   link   *next;
};  

status CreateTree(BiNode** pTree);
status PreOrderTraval(BiNode* pTree);//前序递归
status InOrderTraval(BiNode* pTree);//中序递归
status PostOrderTraval(BiNode* pTree);//后序递归
status st_InOrderTraverse(BiNode* pTree);//中序非递归遍历
void   TreeLink(BiNode* pTree); //队列实现层次遍历
int    TreeHeight (BiNode* pTree);//二叉树的高度
int    Count(BiNode* pTree);//结点个数
int    TreeNumber(BiNode* pTree);//叶子个数
void   Exchange (BiNode* pTree);//交换左右子树
status Visit(char Data);
void   Display(BiNode* pTree,int Level);

BiNode *pRoot=NULL;

status CreateTree(BiNode** pTree) /*Input Example: abd##e##cf##g##*/
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        (*pTree)=NULL;
    }
    else
    {
        if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode))))
        {
            exit(OVERFLOW);
        }
        (*pTree)->Data=ch;
        CreateTree(&((*pTree)->lChild));
        CreateTree(&((*pTree)->rChild));
    }
return OK;
}


status PreOrderTraval(BiNode* pTree)//前序递归
{
    if(pTree)
    {
        if(Visit(pTree->Data))
        {
            if(PreOrderTraval(pTree->lChild))
            {
                if(PreOrderTraval(pTree->rChild))
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}


status InOrderTraval(BiNode* pTree)//中序递归
{
    if(pTree)
    {
        if(InOrderTraval(pTree->lChild))
        {
            if(Visit(pTree->Data))
            {
                if(InOrderTraval(pTree->rChild))
                {
                    return OK;
                }
            }
            return ERROR;
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}


status PostOrderTraval(BiNode* pTree)//后序递归
{
    if(pTree)
    {
        if(PostOrderTraval(pTree->lChild))
        {
            if(PostOrderTraval(pTree->rChild))
            {
                if(Visit(pTree->Data))
                {
                    return OK;
                }
                return ERROR;
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}

status st_InOrderTraverse(BiNode* pTree)//中序非递归遍历
{
	BiNode *p;
	SNode *q,*Stop=NULL;  /*用不带头结点的单链表作为栈的存储结构*/
	p=pTree;
	while(p!=NULL||Stop!=NULL) /*不是空树*/
	{
		if(p!=NULL)
		{
			q=(SNode*)malloc(sizeof(SNode));
			if(q==NULL)return ERROR;
			q->next=Stop;
			q->elem=p;
			Stop=q;  /*根结点指针入栈*/
			p=p->lChild;  /*进入根的左子树*/
		}
		else
		{
			q=Stop;Stop=Stop->next;  /*栈顶元素出栈*/
			printf("%c     ",q->elem->Data);/*访问根结点*/
			p=q->elem->rChild;  /*进入根的右子树*/
			free(q);  /*释放原栈顶元素的结点空间*/
		}
	}
return OK;
}

void   TreeLink(BiNode* pTree) //队列实现层次遍历
{
	struct   link   *head,*rear,*temp;
	head=(struct   link   *)malloc(sizeof(struct   link));   
	head->p=pTree;   
	head->next=NULL;   
	rear=head;   
	do{
		if(head->p->lChild!=NULL)
		{
			temp=(struct   link   *)malloc(sizeof(struct   link)); 
			temp->p=head->p->lChild;   
			temp->next=NULL;   
			rear->next=temp;   
			rear=temp;   
		}   
		if(head->p->rChild!=NULL)   
		{   
			temp=(struct   link   *)malloc(sizeof(struct   link));
			temp->p=head->p->rChild;   
			temp->next=NULL;   
			rear->next=temp;   
			rear=temp;   
		}   
		temp=head;   
		printf("%c     ",head->p->Data);   
		head=head->next;   
		free(temp);   
	}
	while(head!=NULL);
}   


int TreeHeight(BiNode* pTree)//二叉树的高度
{
	int hl ,hr ; //左右子树的高度
	if (pTree == NULL)
		return 0 ;
	else
		hl = TreeHeight(pTree-> lChild);

	hr = TreeHeight (pTree-> rChild);
	if (hl>hr)
		return (hl +1);
	else 
		return (hr +1);
}


int  Count(BiNode* pTree)//结点个数
{
	return  pTree == NULL ? 0 : Count(pTree->lChild) + Count(pTree->rChild) + 1;
}

int  TreeNumber(BiNode* pTree)//叶子个数
{
	if (pTree==NULL)
		return 0; 
	if (pTree->lChild ==NULL && pTree->rChild == NULL)
		return 1; 
	return TreeNumber(pTree->lChild)+TreeNumber(pTree->rChild);//+1就可以求出结点个数
} 

void  Exchange (BiNode* pTree )//交换左右子树
{
	BiNode* temp;
	if ( pTree->lChild != NULL || pTree->rChild != NULL )
	{
		temp = pTree->lChild;
		pTree->lChild = pTree->rChild;
		pTree->rChild = temp;
		Exchange ( pTree->lChild );
		Exchange ( pTree->rChild );
	}

}

status Visit(char Data)
{
    printf("%c     ",Data);
    return OK;
}

void Display(BiNode* pTree,int Level)//显示整个树
{
    int i;
    if(pTree==NULL) return;
    Display(pTree->rChild,Level+1);
    for(i=0;i<Level-1;i++)
    {
        printf(" ");
    }
    if(Level>=1)
    {
        printf("--");
    }
    printf("%c\n",pTree->Data);
    Display(pTree->lChild,Level+1);
}


void CmdList()			//显示命令列表
{
	printf("\n_____________________________________________\n");
	printf("		请选择操作:	\n");
	printf("		1.前序递归遍历\n");		//前序递归遍历
	printf("		2.中序递归遍历\n");		//中序递归遍历
	printf("		3.后序递归遍历\n");		//后序递归遍历	
	printf("		4.中序非递归遍历\n");	//中序非递归遍历
	printf("		5.层次遍历\n");			//层次遍历
	printf("		6.求二叉树高度\n");		//二叉树高度
	printf("		7.求结点个数\n");		//二叉树的结点个数
	printf("		8.求叶子个数\n");		//二叉树的叶子个数
	printf("		9.交换左右子树\n");		//交换左右子树
	printf("		0.退出程序\n");			//退出
	printf("\n______________________________________________\n");

}



void init()
{
	system ("cls"); 
	printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");
	printf("实验三 树和二叉树\n");
	printf("03计本3班\n");
	printf("樊海军 2B0324151138\n");
	printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");
	printf("本程序实现二叉树的常见算法。\n");
	printf("=================================================================\n");
	printf("请输入二叉树各元素:(例如 abd##e##cf##g##)\n"); //例如 abd##e##cf##g##
	CreateTree(&pRoot);   
	Display(pRoot,0);
	CmdList();

}



void ReadCommand(char &c)
{
	do {c=getchar();}
	while (c!='0'&&c!='1'&&c!='2'&&c!='3'&&c!='4'&&c!='5'&&c!='6'&&c!='7'&&c!='8'&&c!='9');
}
void Interpret(char &c)
{
	switch(c)
	{
    case '1':
		{
			printf("\n前序递归遍历:\n");
			PreOrderTraval(pRoot);
			CmdList();
			break;
		}
	case '2':
		{
			printf("\n中序递归遍历:\n");
			InOrderTraval(pRoot);
			CmdList();
			break;
		}
	case '3':
		{
			printf("\n后序递归遍历:\n");
			PostOrderTraval(pRoot);
			CmdList();
			break;
		}
	case '4':
		{
			printf("\n中序非递归遍历:\n");
			st_InOrderTraverse(pRoot);
			CmdList();
			break;
		}
	case '5':
		{
			printf("\n层次遍历:\n");
			TreeLink(pRoot);
			CmdList();
			break;
		}
	case '6':
		{
			printf("\n二叉树高度:\n");
			printf("%d\n",TreeHeight(pRoot));
			CmdList();
			break;
		}
	case '7':
		{
			printf("\n结点个数:\n");
			printf("%d\n",Count(pRoot));
			CmdList();
			break;
		}
	case '8':
		{
			printf("\n叶子个数:\n");
			printf("%d\n",TreeNumber(pRoot));
			CmdList();
			break;
		}
	case '9':
		{
			printf("\n交换左右子树:\n");
			Exchange(pRoot);
			printf("\n交换后的二叉树:\n");
			Display(pRoot,0);
			CmdList();
			break;
		}
	case '0': printf("程序结束，按任意键退出!\n"); 
       }

}


void main() //主函数
{
	char cmd;
	init();
	do
	{
		ReadCommand(cmd);
		Interpret(cmd);
	}
	while (cmd!='0'&&cmd!='0');
}