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

//二叉樹的鏈?zhǔn)酱鎯?chǔ)表示
typedef char DataType;		//應(yīng)由用戶定義DataType的實(shí)際類型
typedef struct node
{	DataType data;
	struct node *lchild, *rchild;	//左右孩子指針
} BinTNode;					//結(jié)點(diǎn)類型
typedef BinTNode *BinTree;

void main()
{
	void ListBinTree(BinTree T);	//用廣義表表示二叉樹
	void DisplayBinTree(BinTree T);	//用凹入表表示二叉樹
	void CreateBinTree(BinTree *T);	//構(gòu)造二叉鏈表
	BinTree T;
	printf("請(qǐng)輸入先序序列（虛結(jié)點(diǎn)用空格表示）：\n");
	CreateBinTree(&T);
	ListBinTree(T);
	printf("\n");
	DisplayBinTree(T);
}

//構(gòu)造二叉鏈表
void CreateBinTree(BinTree *T)
{
	char ch;
	if ((ch=getchar())==' ')
		*T=NULL;
	else
	{	//讀入非空格
		*T=(BinTNode *)malloc(sizeof(BinTNode));	//生成結(jié)點(diǎn)
		(*T)->data=ch;
		CreateBinTree(&(*T)->lchild );			//構(gòu)造左子樹
		CreateBinTree(&(*T)->rchild );			//構(gòu)造右子樹
	}
}

//用廣義表表示二叉樹
void ListBinTree(BinTree T)
{
	if (T!=NULL)
	{
		printf("%c",T->data);
		if (T->lchild!=NULL||T->rchild!=NULL)
		{
			printf("(");
			ListBinTree(T->lchild);
			if (T->rchild!=NULL)
				printf(",");
			ListBinTree(T->rchild);
			printf(")");
		}
	}
}

//用凹入表表示二叉樹
void DisplayBinTree(BinTree T)
{
	BinTree stack[100],p;
	int level[100],top,n,i;
	if (T!=NULL)
	{
		printf("用凹入表表示二叉樹:\n");
		top=1;
		stack[top]=T;
		level[top]=3;
		while(top>0)
		{
			p=stack[top];
			n=level[top];
			for (i=1;i<=n; i++)
				printf(" ");
			printf("%c\n",p->data);
			top--;
			if (p->rchild!=NULL)
			{
				top++;
				stack[top]=p->rchild;
				level[top]=n+3;
			}
			if (p->lchild!=NULL)
			{
				top++;
				stack[top]=p->lchild;
				level[top]=n+3;
			}
		}
	}
}