二叉樹的各種操作復習

[cpp] 
/*二叉樹的各種操作復習*/ 
#include <stdio.h> 
 
#define BACK_ODER   -1 
#define IN_ODER     0 
#define PRE_ODER    1 
#define LEVEL_ODER  2//層次化遍歷 
typedef struct _Node{ 
    char data; 
    struct _Node *lchild; 
    struct _Node *rchild; 
} Node,*Tree; 
 
/* 生成二叉樹的普通方法
 * 按先序次序輸入二叉樹中結點的值
 * 構造二叉鏈表表示的二叉樹T。輸入空格表示空子樹。 */ 
Node * CreateTree() 
{ 
    char ch; 
    scanf("%c",&ch); 
    Node *T; 
 
    if(ch==' ') /* 空 */ 
        return NULL; 
    else 
    { 
        T=(Node *)malloc(sizeof(Node)); 
        if(!T) 
            exit(0); 
        T->data=ch; /* 生成根結點 */ 
        T->lchild = CreateTree(); /* 構造左子樹 */ 
        T->rchild = CreateTree(); /* 構造右子樹 */ 
    } 
    return T; 
} 
/* 由先根序列和中根序列生成二叉樹
 * 遞歸法。pre 是先跟序列，in是中根序列
 * pre_s是先根序列的起始，pre_e是先跟序列的結束
 * in_s是中根序列的起始,in_e是中根序列的結束
 */ 
Node *Convert(char pre[], int pre_s, int pre_e, 
              char in [], int in_s , int in_e ) 
{ 
    if(in_s > in_e)return NULL; 
 
    int i = in_s; 
    for(i=in_s;i<in_e&&in[i]!=pre[pre_s];i++); 
 
 
    Node *p = (Node *)malloc(sizeof(Node)); 
    p->data = pre[pre_s]; 
    p->lchild = Convert(pre, pre_s+1, pre_s+i-in_s, 
                        in,  in_s,i-1); 
    p->rchild = Convert(pre, pre_s+i-in_s+1,pre_e, 
                        in,  i+1,in_e); 
 
    return p; 
} 
/*求二叉樹的度*/ 
int GetDegree(const Tree head) 
{ 
    int degree = 0; 
    int m,n; 
    if(!head)return 0; 
 
    if(head->lchild && head->rchild) return 2; 
    else if(!head->lchild && !head->rchild) return 0; 
    else { 
        m = GetDegree(head->lchild) ; 
        n = GetDegree(head->rchild) ; 
        if(2==m || 2==n)return 2; 
        else return 1; 
    } 
    return degree; 
} 
/*求二叉樹的高度*/ 
int GetHight(const Tree head) 
{ 
    int m,n; 
 
    if(!head)return 0; 
 
    m = GetHight(head->lchild); 
    n = GetHight(head->rchild); 
 
    return 1 + (m > n ? m : n); 
 
} 
/* 輸出二叉樹中某個指定元素的祖父節點(包括自己)
 * 遞歸思想：如果此節點在其子樹中，那麼它是祖父節點
 * 返回值 ：1表示子樹中有 ，0表示無*/ 
int GetGrandPa(const Tree head, const char e) 
{ 
   if(!head)return 0; 
 
   if(GetGrandPa(head->lchild,e) || GetGrandPa(head->rchild,e) || e==head->data)//子樹中有此節點 
   { 
       printf("%c",head->data); 
       return 1; 
   } 
   else return 0; 
} 
/*遍歷二叉樹，參數oder控制遍歷方式*/ 
void Tranverse(Node *head,int oder) 
{ 
    if(!head)return ; 
    if(LEVEL_ODER == oder) 
    { 
        LevTranverse(&head,1); 
        return; 
    } 
 
    if(PRE_ODER == oder) printf("%c\t",head->data); 
    Tranverse(head->lchild,oder); 
    if(IN_ODER == oder) printf("%c\t",head->data); 
    Tranverse(head->rchild,oder); 
    if(BACK_ODER == oder) printf("%c\t",head->data); 
    return; 
} 
/* 層次化遍歷，采用遞歸思想而不用隊列。
 * 遞歸思想：把當前層遍歷的同時把下一層存儲好
 * nodes[]存儲的當前層的節點，count表示當前層的元素個數*/ 
void LevTranverse(const Node* nodes[], int count) 
{ 
    int i=0, j=0; 
 
    if(0 == count) return; 
 
    Node *nextNodes[100] = {0}; 
    for(i = 0,j=0; i<count; i++) 
    { 
        printf("%c\t",nodes[i]->data); 
        if(nodes[i]->lchild)nextNodes[j++] = nodes[i]->lchild; 
        if(nodes[i]->rchild)nextNodes[j++] = nodes[i]->rchild; 
    } 
    LevTranverse(nextNodes,j); 
    return; 
} 
 
int main(int argc, char *argv[]) 
{   www.2cto.com
    char pre[]= "abcde"; 
    char in[] = "bcade"; 
    Node *head = NULL; 
 
    head = Convert(pre,0,strlen(pre)-1, 
                   in ,0,strlen(in)-1); 
 
    printf("Hight : %d\n",GetHight(head)); 
    printf("Degree : %d\n",GetDegree(head)); 
    if(!GetGrandPa(head,'c'))printf("No grandpa !");printf("\n"); 
    Tranverse(head,LEVEL_ODER);printf("\n"); 
     
    system("PAUSE"); 
}