Title : BinTree.c
Author : 张龙
Time : 200508
*****************************************************************/
#include
/*=========================== data struct =====================*/
typedef char ElementType;
typedef struct Node{
ElementType data;
struct Node *LChild; /* LeftChild */
struct Node *RChild; /* RightChild */
} TreeNode;
/*=============================== function declaration ===============*/
int CreateBinTree( TreeNode **rootp,ElementType **lp );
void FreeTree( TreeNode *rootp );
int DelSubTree( TreeNode *rootp,ElementType e );
int Insert( TreeNode *rootp,ElementType Curr,ElementType e,int CurrPos );
TreeNode *FindNode( TreeNode *rootp,ElementType e );
TreeNode *FindParent( TreeNode *rootp,ElementType e );
void Leaf( TreeNode *rootp,int *np );
int Depth( TreeNode *rootp );
void PreOrder( TreeNode *rootp );
void InOrder( TreeNode *rootp );
void PostOrder( TreeNode *rootp );
/*================================ function implementation ================*/
/*------------------------------------------------------ CreateTree -------*/
int CreateBinTree( TreeNode **rootp,ElementType **lp )
{
ElementType CurrElement;
if(*lp==NULL) return 0; /* string isn't exist */
if(**lp==0) return 1; /* empty string */
printf("hello1\n");
CurrElement=**lp;
printf("hello2\n");
(*lp)++;
printf("hello3\n");
if(CurrElement=='.'){
(*rootp)=NULL;
return 1;
}
if(!((*rootp)=(TreeNode *) malloc(sizeof(TreeNode))) ) return 0;
(*rootp)->data=CurrElement;
printf("the value of node is %c\n",(*rootp)->data);
printf("hello4\n");
if(!CreateBinTree(&(*rootp)->LChild,lp)) return 0;
return CreateBinTree(&(*rootp)->RChild,lp);
}
/*------------------------------------------------------- FreeTree --------*/
void FreeTree( TreeNode *rootp )
{
if(!rootp) return;
FreeTree(rootp->LChild);
FreeTree(rootp->RChild);
free(rootp);
}
/*-------------------------------------------------------- DelSubTree --------*/
int DelSubTree( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
temp=FindParent(rootp,e);
if(!temp) return 0;
if(temp->LChild &&(temp->LChild->data==e)){
FreeTree(temp->LChild);
temp->LChild=NULL;
}
else{
FreeTree(temp->RChild);
temp->RChild=NULL;
}
return 1;
}
/*-------------------------------------------------------- Insert --------*/
int Insert( TreeNode *rootp,ElementType Curr,ElementType e,int CurrPos )
{
TreeNode *parent,*new,*temp;
if(!(parent=FindParent(rootp,Curr))) return 0;
if(!(new=(TreeNode *) malloc(sizeof(TreeNode)))) return 0;
new->data=e;
if(parent->LChild->data==Curr){
temp=parent->LChild;
parent->LChild=new;
}
if(parent->LChild->data==Curr){
temp=parent->RChild;
parent->RChild=new;
}
if(CurrPos==0){
new->LChild=temp;
new->RChild=NULL;
}
if(CurrPos==1){
new->RChild=temp;
new->LChild=NULL;
}
return 1;
}
/*------------------------------------------------------- FindNode --------*/
TreeNode *FindNode( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
if(rootp==NULL) return NULL; /* if(!rootp) */
if(rootp->data==e) return rootp;
if(temp=FindNode(rootp->LChild,e)) return temp;
return FindNode(rootp->RChild,e);
}
/*----------------------------------------------------- FindParent --------*/
TreeNode *FindParent( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
if((rootp==NULL)||(rootp->LChild==NULL && rootp->RChild==NULL)) return NULL;
if((rootp->LChild && rootp->LChild->data==e)||(rootp->RChild && rootp->RChild->data==e))
return rootp;
temp=FindParent(rootp->LChild,e);
if(temp) return temp;
return FindParent(rootp->RChild,e);
}
/*----------------------------------------------------------- Leaf --------*/
void Leaf( TreeNode *rootp,int *np )
{
if(rootp==NULL) return ;
if(rootp->LChild==NULL && rootp->RChild==NULL){
(*np)++;
return;
}
Leaf(rootp->LChild,np);
Leaf(rootp->RChild,np);
}
/*---------------------------------------------------------- Depth --------*/
int Depth( TreeNode *rootp ){
int ld,rd; /* ld: LeftChild's depth */ /* rd: RightChild's depth */
if(rootp==NULL) return 0;
ld=Depth(rootp->LChild);
rd=Depth(rootp->RChild);
if(ld>rd)
return ld+1;
else
return rd+1;
}
/*------------------------------------------------------- PreOrder --------*/
void PreOrder( TreeNode *rootp )
{
if(rootp==NULL) return; printf(" %c",rootp->data); /* show parent */
if(rootp->LChild!=NULL) PreOrder(rootp->LChild); /* show LeftChild */
if(rootp->RChild!=NULL) PreOrder(rootp->RChild); /* show RightChild */
return;
}
/*--------------------------------------------------------InOrder --------*/
void InOrder( TreeNode *rootp )
{
if(rootp==NULL) return;
if(rootp->LChild!=NULL) InOrder(rootp->LChild);
printf(" %c",rootp->data);
if(rootp->RChild!=NULL) InOrder(rootp->RChild);
return;
}
/*------------------------------------------------------ PostOrder --------*/
void PostOrder( TreeNode *rootp )
{
if(rootp==NULL) return;
if(rootp->LChild!=NULL) PostOrder(rootp->LChild);
if(rootp->RChild!=NULL) PostOrder(rootp->RChild);
printf(" %c",rootp->data);
return;
}
/*========================main function===================*/
int main(int argc,char *argv[])
{
TreeNode **mytree;
char *x="abcdefghijklmn";
ElementType **lp;
printf("hello\n");
lp=&x;
printf("%s\n",*lp);
CreateBinTree(mytree,lp);
printf("\nthe depth of tree is %d\n",Depth(*mytree));
printf("\nthe PreOrder is : \n");
PreOrder(*mytree);
printf("\nthe InOrder is : \n");
InOrder(*mytree);
printf("\nthe PostOrder is : \n");
PostOrder(*mytree);
TreeNode * temp;
temp=FindParent(*mytree,'c');
printf("\nthe parent of c is %c\n",temp->data);
Insert(*mytree,'h','o',1);
printf("\nthe depth of tree is %d\n",Depth(*mytree));
printf("\nthe PreOrder is : \n");
PreOrder(*mytree);
printf("\nthe InOrder is : \n");
InOrder(*mytree);
printf("\nthe PostOrder is : \n");
PostOrder(*mytree);
DelSubTree(*mytree,'e');
printf("\nthe depth of tree is %d\n",Depth(*mytree));
printf("\nthe PreOrder is : \n");
PreOrder(*mytree);
printf("\nthe InOrder is : \n");
InOrder(*mytree);
printf("\nthe PostOrder is : \n");
PostOrder(*mytree);
return 1;
}