建立二叉树.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 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 Preorder(BinTree T)
{
	if(T)
	{
		printf("%c",T->data);	/*访问结点  */
		Preorder(T->lchild);
		Preorder(T->rchild);
	}
}
main()
{
	
	BinTree T;
	printf("请输入先序序列（虚结点用空格表示）：\n");
	CreateBinTree(&T);
	ListBinTree(T);
	printf("\n");
	DisplayBinTree(T);
	printf("前序遍历：\n");
	Preorder(T);
	printf("\n");
}