데이터 구조 - 트 리 관련 알고리즘 구현

#include 
#include 
#define MAXSIZE 30

typedef char ElemType;

typedef struct TNode {
    char data;
    TNode * lchild; 
    TNode * rchild;
}TNode, *BiTree;


int IsEmpty_BiTree(BiTree *T) {
    if(*T == NULL)
    return 1;//            ，         
    else
    return 0;
}

void Create_BiTree(BiTree *T){
    char ch;
    ch = getchar();
    //     "#" ，       
    if(ch == '#')
        *T = NULL;
    //     
    else{
        *T = (BiTree)malloc(sizeof(struct TNode));
        (*T)->data = ch; //     
        //     
        Create_BiTree(&(*T)->lchild);
        //     
        Create_BiTree(&(*T)->rchild);
    }
}

void TraverseBiTree(BiTree T) { //     
    if(T == NULL)//    ，        
    return; 
    else {
        printf("%c ",T->data);
        TraverseBiTree(T->lchild);
        TraverseBiTree(T->rchild);
    }
    
}

void InOrderBiTree(BiTree T) {      //     
    if(NULL == T)
    return;
    else {
        InOrderBiTree(T->lchild);
        printf("%c ",T->data);
        InOrderBiTree(T->rchild);   
    }
}

void PostOrderBiTree(BiTree T) {
    if(NULL == T)
    return;
    else {
        InOrderBiTree(T->lchild);
        InOrderBiTree(T->rchild);
        printf("%c ",T->data);
    }
    
} 

int TreeDeep(BiTree T) {
    int deep = 0;
    if(T)
    {
        int leftdeep = TreeDeep(T->lchild);
        int rightdeep = TreeDeep(T->rchild);
        deep = leftdeep+1 > rightdeep+1 ? leftdeep+1 : rightdeep+1; 
    }
    return deep;
}
//        
int Leafcount(BiTree T, int &num) {//              
    if(T)
    {
        if(T->lchild ==NULL && T->rchild==NULL) 
        {
            num++;
            printf("%c ",T->data);
        }           
        Leafcount(T->lchild,num);
        Leafcount(T->rchild,num);

    }
    return num;
}

//       （    ，             ） 
void LevelOrder_BiTree(BiTree T){
    //           ,                   
    int front = 0;
    int rear = 0;
    BiTree BiQueue[MAXSIZE];
    BiTree tempNode;
    if(!IsEmpty_BiTree(&T)){
        BiQueue[rear++] = T;
         
        while(front != rear){// 
            //      ，            　
            tempNode = BiQueue[front++];
            //          ,    ，     　
            if(!IsEmpty_BiTree(&(tempNode->lchild)))
                BiQueue[rear++] = tempNode->lchild;
             
            if(!IsEmpty_BiTree(&(tempNode->rchild)))
                BiQueue[rear++] = tempNode->rchild;
             
             printf("%c ",tempNode->data);
        }
    }
}

int main(void)
{
    BiTree T;
    BiTree *p = (BiTree*)malloc(sizeof(BiTree));
    int deepth,num=0 ;
    Create_BiTree(&T);//              
    printf("       :
");
    TraverseBiTree(T);
    printf("
");
    printf("       :
");
    InOrderBiTree(T);
    printf("
");
    printf("       :
");
    PostOrderBiTree(T);
    printf("
      ：");
    LevelOrder_BiTree(T);
    printf("
");
    deepth=TreeDeep(T);
    printf("     :%d",deepth);
    printf("
");
    printf("       :");
    Leafcount(T,num);
    printf("
         :%d",num);
    return 0;
}

#include
#include 
using namespace std;

typedef struct BiThrNode
{
    char data;
    struct BiThrNode *lchild,*rchild;      /*      */
    int LTag,RTag;                          /*    */
}BiThrNode,*BiThrTree;

BiThrTree pre;



void CreateBiTree(BiThrTree *T){
    char ch;
    ch = getchar();
    //     "#" ，       
    if(ch == '#')
        *T = NULL;
    //     
    else{
        *T = (BiThrTree)malloc(sizeof(struct BiThrNode));
        (*T)->data = ch; //     
        //     
        CreateBiTree(&(*T)->lchild);
        //     
        CreateBiTree(&(*T)->rchild);
    }
}

/*   p          */
void InThreading(BiThrTree p)
{
    /*pre     ，            ，             */
    if(p)
    {
        InThreading(p->lchild);            /*        */
        if(!(p->lchild) )                      /*p      */
        {                  
            p->LTag=1;                     /* p     */
            p->lchild=pre;                 /*p        pre(  )*/
        }
        else
        {
            p->LTag=0;
        }
        if(!(pre->rchild) )                  /*pre      */
        {
            pre->RTag=1;                  /* pre     */
            pre->rchild=p;                /*pre        p(  )*/
        }
        else
        {
            pre->RTag=0;
        }
        pre=p;                            /*  pre  p   */
        InThreading(p->rchild);           /*        */
    }
}
/*          */
void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    /*       T，        ，Thrt     */
    Thrt=new BiThrNode;         /*    */
    Thrt->LTag=0;               /*       ，    ，        */       
    Thrt->RTag=1;               /*             */
    Thrt->rchild=Thrt;          /*           */
    if(!T) Thrt->lchild=Thrt;   /*    ，         */
    else
    {
        Thrt->lchild=T; pre=Thrt; /*          ，pre       */
        InThreading(T);          /*      ，  T             */
        pre->rchild=Thrt;        /*     ，pre     ，pre         */
        pre->RTag=1;
        Thrt->rchild=pre;        /*         pre*/
    } 
}  
/*         */
void InOrderTraverse_Thr(BiThrTree T)
{
    /*T     ，      lchild     */
    /*         T      ，           */
    BiThrTree p=T->lchild;    /*p     */        
    while(p!=T)
    {
        while(p->LTag == 0)      /*      */
        {
             p=p->lchild;
        }
        cout<data<RTag == 1 && p->rchild!=T)  /*          */
        {
            p=p->rchild;
            cout<data<rchild;
    }
    cout<data;
}
int main()
{
    BiThrTree T;
    BiThrTree Thrt;
    cout<