建立树2.cpp

这里面包括数据结构多数的算法

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

//二叉树的链式存储表示
typedef char DataType;		//应由用户定义DataType的实际类型
typedef struct node
{	DataType data;
	struct node *lchild, *rchild;	//左右孩子指针
} BinTNode;					//结点类型
typedef BinTNode *BinTree;

void main()
{
	void ListBinTree(BinTree T);	//用广义表表示二叉树
	void DisplayBinTree(BinTree T);	//用凹入表表示二叉树
	void CreateBinTree(BinTree *T);	//构造二叉链表
	void Postorder(BinTree T);		//后序遍历二叉树
	BinTree T;
	printf("请输入先序序列（虚结点用空格表示）：\n");
	CreateBinTree(&T);
	ListBinTree(T);
	printf("\n");
	DisplayBinTree(T);
	printf("后序遍历：\n");
	Postorder(T);
	printf("\n");
}

//构造二叉链表
void CreateBinTree(BinTree *T)
{
	char ch;
	if ((ch=getchar())==' ')
		*T=NULL;
	else
	{	//读入非空格
		*T=(BinTNode *)malloc(sizeof(BinTNode));	//生成结点
		(*T)->data=ch;
		CreateBinTree(&(*T)->lchild );			//构造左子树
		CreateBinTree(&(*T)->rchild );			//构造右子树
	}
}

//用广义表表示二叉树
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;
			}
		}
	}
}

//后序遍历二叉树
void Postorder(BinTree T)
{
	if(T)
	{
		Postorder(T->lchild);
		Postorder(T->rchild);
		printf("%c",T->data);	//访问结点
	}
}