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

3728 단어
한 네티즌 csdn을 종합하고 을 결합한다.
그중에서 나는 귀속에 대한 이해도 한쪽에 주석을 달았다.
안타깝게도 이 프로그램은 실행될 수 없다.그러나 큰소리 데이터 구조의 코드는 뛸 수 있지만 이것에 얽매일 필요는 없다. 핵심을 파악하면 된다.
 
#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; }

좋은 웹페이지 즐겨찾기