두 갈래 나무 - 체인 테이블 구조

 
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"

#define MAXSIZE 100
typedef int Status;
typedef char TElemType;
typedef char String[30];//0       

String StrT;//      
int pos=1;
TElemType Nil=' ';

typedef struct BiLTNode  //     
{
	TElemType data;
	struct BiLTNode *lchild,*rchild;
}BiLTNode,*BiLTree;

Status InitBiLTree(BiLTree *T)
{
	//       
	*T=NULL;
	return 1;
}

Status Visit(TElemType e)
{
	//    
	printf("%d",e);
	return 1;
}

/ *     * /  

//          ，        ，
//  CreateBiLTree()   ，    
//       ，              
//      ，     。

Status StrAssign(String StrT,char *s)
{
	int i;
	int j;
	j=strlen(s);
	if (j>MAXSIZE)
		return 0;

	else{
		StrT[0]=j;
		for (i=1;i<=j;i++){
			StrT[i]=*(s+i-1);
		}

		return 1;
	}
}

//     ：         ，        
//         ，  
//     else                  
//        ，         ，  
//《      》      

Status CreateBiLTree(BiLTree *T)
{
	TElemType ch;
	if(*T==NULL)
		return 0 ;
	
	ch=StrT[pos++];

	if (ch=='#')
		*T=NULL;
	else	
	{
		*T=malloc(sizeof(struct BiLTNode));

		if (*T==NULL)
		{
			exit(1);
		}
		else	
		{
			(*T)->data=ch;
			CreateBiLTree(&(*T)->lchild);
			CreateBiLTree(&(*T)->rchild);

			return 1;
		}
	}
}
/ *       * /  

Status DestroyBiLTree(BiLTree *T)
{
	if (*T==NULL)
		return 0;

	if ((*T)->lchild)
		DestroyBiLTree(&(*T)->lchild);

	if ((*T)->rchild)
		DestroyBiLTree(&(*T)->rchild);

	free(*T);
	//      , *T      .   *T  ,   *T=NULL;  
	//free malloc  ,        *T       ,   
    // *T=NULL          
	*T=NULL;
	return 1;
}

int DepthBiLTree(BiLTree *T)
{
	int ldepth,rdepth;
	if (*T==NULL)
		return 0;

	if (!(*T)->lchild&&!(*T)->rchild)
		return 1;

	else{

		ldepth=DepthBiLTree(&(*T)->lchild);
		rdepth=DepthBiLTree(&(*T)->rchild);

		return (ldepth>rdepth?ldepth:rdepth)+1;

		//    1  .     2,  
		//       *T   ,  
		//    *T *T   ,        2.  
        //  ,ldepth rdepth  ,       

//      ，          ，         
//   ，      ，     ，      ，    
//  。        ，            ，        ， 
//       ，  +1

	}
}

TElemType Root(BiLTree *T)
{
	if (*T==NULL)
		return Nil;

	return (*T)->data;
}


void PreOrderTraverse(BiLTree *T)
{
	if(*T==NULL)
		exit(1);
	Visit((*T)->data);
	PreOrderTraverse(&(*T)->lchild);
	PreOrderTraverse(&(*T)->rchild);
}

void InOrderTraverse(BiLTree *T)
{
	if ((*T)==NULL)
		exit(1);

	InOrderTraverse(&(*T)->lchild);
	Visit((*T)->data);
	InOrderTraverse(&(*T)->rchild);
}

void PostOrderTraver(BiLTree *T)
{
	if ((*T)==NULL)
		exit(1);

	PostOrderTraver(&(*T)->lchild);
	PostOrderTraver(&(*T)->rchild);
	Visit((*T)->data);
}
int main()
{
	char *chars = "ABCD#K###E##CFI###G#J##";//      
    StrAssign(StrT,chars); 
    BiLTree *T;//T     
	 
    T = (BiLTree *)malloc(sizeof(BiLTree));  
    InitBiLTree(T);  
    CreateBiLTree(T);  
    printf("      ,       （1： ,0：  ）？ %d
",EmptyBiLTree(T));  
    printf("        %d
",DepthBiLTree(T));  
    printf("      ：%c
",Root(T));  
	
    printf("      ：");  
    PreOrderTraverse(T);  
    printf("
");  
	
    printf("      ：");  
    InOrderTraverse(T);  
    printf("
");  
	
    printf("      ：");  
    PostOrderTraverse(T);  
    printf("
");  
	
    //     
    DestoryBiLTree(T);  
    printf("      ,       （1： ,0：  ）？ %d
",EmptyBiLTree(T)); 
	return 0;
}