1.c

来自「建立一棵二叉树」· C语言 代码 · 共 100 行

#include<stdio.h>
#include<stdlib.h>
#define QueueMaxSize 20
#define StackMaxSize 20
typedef char ElemType;
struct BTreeNode
{
	ElemType data;
	struct BTreeNode* left;
    struct BTreeNode* right;

};
void Preorder(struct BTreeNode* BT)
{
	if(BT!=NULL)
	{
		printf("%c",BT->data);
		Preorder(BT->left);
        Preorder(BT->right);
	}
}
void Inorder(struct BTreeNode* BT)
{
	if(BT!=NULL)
	{
		Inorder(BT->left);
        printf("%c",BT->data);
        Inorder(BT->right);
	}
}
void Postorder(struct BTreeNode* BT)
{
	if(BT!=NULL)
	{
		Postorder(BT->left);
        Postorder(BT->right);
	    printf("%c",BT->data);
	}
}
void CreateBTree(struct BTreeNode** BT,char* a)
{
	struct BTreeNode* p;
    struct BTreeNode* s[StackMaxSize];
	int top=-1;
	int k;
	int i=0;
	*BT=NULL;
	while (a[i])
	{
		switch(a[i])
		{
		case' ':
			break;
		case'(':
			if(top==StackMaxSize-1)
			{
				printf("栈空间太小，需增加StackMaxSize!\n");
				exit(1);
			}
			top++;s[top]=p;k=1;
			break;
		case')':
			if(top==-1)
			{
				printf("二叉树广义表字符串错!\n");
				exit(1);
			}
			top--;break;
		case',':
			k=2;break;
		default:
			p=malloc(sizeof(struct BTreeNode));
			p->data=a[i];p->left=p->right=NULL;
			if(*BT==NULL) *BT=p;
			else
			{
			if(k==1)  s[top]->left=p;
			else s[top]->right=p;
			}
		}
		i++;
	}
}
void main()
{
	struct BTreeNode* bt;
	char b[50];
	printf("输入二叉树广义表字符串：\n");
	scanf("%s",b);
	CreateBTree(&bt,b);
	printf("前序：");
	Preorder(bt);
	printf("\n");
    printf("中序：");
	Inorder(bt);
	printf("\n");
    printf("后序：");
	Postorder(bt);
	printf("\n");
}