データ構造-ツリー-中順再帰ツリー(シーケンス構造)

#include <stdio.h> /* EOF(=^Z F6),NULL */
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status      ,           ， OK  */

#if CHAR
typedef char TElemType;
TElemType Nil=' '; /*            */
#else
typedef int TElemType;
TElemType Nil=0; /*     0   */
#endif

#define MAX_TREE_SIZE 100 /*           */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0         */

Status InitBiTree(SqBiTree T)
{ /*       T。  T     ，    ，    & */
	int i;
	for(i=0;i<MAX_TREE_SIZE;i++)
		T[i]=Nil; /*      */
	return OK;
}

Status CreateBiTree(SqBiTree T)
{ /*                (      ),           T */
	int i=0;
#if CHAR
	int l;
	char s[MAX_TREE_SIZE];
	printf("          (  )，       ，   ≤%d:
",MAX_TREE_SIZE);
	gets(s); /*       */
	l=strlen(s); /*         */
	for(;i<l;i++) /*        T */
	{
		T[i]=s[i];
		if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /*    (  )        */
		{
			printf("          %c
",T[i]);
			exit(ERROR);
		}
	}
	for(i=l;i<MAX_TREE_SIZE;i++) /*      T       */
		T[i]=Nil;
#else
	printf("          (  )，0     ， 999  。   ≤%d:
",MAX_TREE_SIZE);
	while(1)
	{
		scanf("%d",&T[i]);
		if(T[i]==999)
			break;
		if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /*    (  )        */
		{
			printf("          %d
",T[i]);
			exit(ERROR);
		}
		i++;
	}
	while(i<MAX_TREE_SIZE)
	{
		T[i]=Nil; /*      T       */
		i++;
	}
#endif
	return OK;
}

Status BiTreeEmpty(SqBiTree T)
{ /*     :    T   */
	/*     :  T     ,   TRUE,  FALSE */
	if(T[0]==Nil) /*      ,    */
		return TRUE;
	else
		return FALSE;
}

Status(*VisitFunc)(TElemType); /*      */

void InTraverse(SqBiTree T,int e)
{ /* InOrderTraverse()   */
	if(T[2*e+1]!=Nil) /*       */
		InTraverse(T,2*e+1);
	VisitFunc(T[e]);
	if(T[2*e+2]!=Nil) /*       */
		InTraverse(T,2*e+2);
}
Status InOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
{ /*     :      ,Visit            */
	/*     :     T,         Visit      。 */
	/*             Visit()  ,      */
	VisitFunc=Visit;
	if(!BiTreeEmpty(T)) /*     */
		InTraverse(T,0);
	printf("
");
	return OK;
}

Status visit(TElemType e)
{
	printf("%d ",e);
	return OK;
}

void main()
{
	SqBiTree T;
	InitBiTree(T);
	CreateBiTree(T);
	printf("       :
");
	InOrderTraverse(T,visit);//       
}