樹(shù)(Tree)
定義

    樹(shù)(Tree) 是n個(gè)(n≥0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱(chēng)為空樹(shù)。
    在任何一個(gè)非空樹(shù)中：
        (1) 有且僅有一個(gè)特定的稱(chēng)為根(root)的結(jié)點(diǎn)；
        (2) 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集。(子樹(shù)) 

結(jié)點(diǎn)分類(lèi)

    結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為結(jié)點(diǎn)的度(Degree)； 
    度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)(Leaf) 或終端結(jié)點(diǎn)；
    度不為0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)；
    除根結(jié)點(diǎn)之外，分支結(jié)點(diǎn)也稱(chēng)為內(nèi)部結(jié)點(diǎn)；
    樹(shù)的度是樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。 

抽象數(shù)據(jù)類(lèi)型

ADT 樹(shù)(tree) 
Data 
    樹(shù)是由一個(gè)根結(jié)點(diǎn)和若干棵子樹(shù)構(gòu)成。數(shù)中結(jié)點(diǎn)具有相同的數(shù)據(jù)類(lèi)型和層次關(guān)系 
Operation
    InitTree(*T):
    DestroyTree(*T):
    CreatTree(*T,definition):
    ClearTree(*T):
    TreeEmpty(T):
    TreeDepth(T): 
    Root(T):
    Value(T,cur_e):
    Assign(T,cur_e,value):
    parent(T,cur_e):
    LeftChild(T,cur_e):
    RightSibling(T,cur_e):
    InsertChild(*T,*p,i,c):
    DeleteChild(*T,*p,i):
endADT

樹(shù)的存儲(chǔ)結(jié)構(gòu)

雙親表示法:在每個(gè)結(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在數(shù)組中的位置

//  樹(shù)的雙親表示法結(jié)點(diǎn)結(jié)構(gòu)定義
#define MAX_TREE_SIZE 100

typedef char TElemType;             /*樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型*/ 
typedef struct PTNode{              /*結(jié)點(diǎn)結(jié)構(gòu)*/ 
    TElemType data;                 /*結(jié)點(diǎn)數(shù)據(jù)*/ 
    int parent;                     /*雙親位置*/ 
}PTNode;

typedef struct{                     /*樹(shù)結(jié)構(gòu)*/ 
    PTNode nodes[MAX_TREE_SIZE];    /*結(jié)點(diǎn)數(shù)組*/ 
    int r,n;                        /*根的位置和結(jié)點(diǎn)數(shù)*/ 
}PTree;

每個(gè)結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹(shù)的根結(jié)點(diǎn)。(多重鏈表表示法)造成浪費(fèi)

孩子表示法：把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，以單鏈表作存儲(chǔ)結(jié)構(gòu)。則n個(gè)孩子有n個(gè)孩子鏈表。
如果是葉子結(jié)點(diǎn)則此單鏈表為空，然后n個(gè)頭指針又組成一個(gè)線(xiàn)性表，采用順序存儲(chǔ)結(jié)構(gòu)，存放進(jìn)一個(gè)一維數(shù)組。

//  樹(shù)的孩子表示法結(jié)構(gòu)定義
#define MAX_TREE_SIZE 100
typedef struct CTNode{      /* 孩子結(jié)點(diǎn) */ 
    int child;
    struct CTNode *next;
}*ChilePtr; 
typedef struct{             /* 表頭結(jié)構(gòu) */ 
    TElemType data;
    ChildPtr firstchild;
}CTBox;
typedef struct{             /* 樹(shù)結(jié)構(gòu) */ 
    CTBox nodes[MAX_TREE_SIZE];
    int r,n;                /* 根的位置和結(jié)點(diǎn)數(shù) */ 
}Ctree;

孩子兄弟表示法：任意一棵樹(shù)，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此，設(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此結(jié)點(diǎn)的右兄弟。

//  樹(shù)的孩子表示法結(jié)構(gòu)定義 
typedef struct CSNode {
    TElemType data;
    struct CSNode *firstchild,*rightsib;
}CSNode,*CSTree;

二叉樹(shù)(Binary Tree)
是n個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的，分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

特點(diǎn)：

滿(mǎn)二叉樹(shù)：   
    在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上，這樣的樹(shù)叫~；
完全二叉樹(shù)：
    對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i的結(jié)點(diǎn)與同樣深度的滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。

滿(mǎn)二叉樹(shù)一定是一棵完全二叉樹(shù)，但是完全二叉樹(shù)不一定是滿(mǎn)的。

滿(mǎn)二叉樹(shù)特點(diǎn)：
    葉子只能出現(xiàn)在最下一層；
    非葉子結(jié)點(diǎn)的度一定是2；
    在同樣深度的二叉樹(shù)中，滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多，葉子數(shù)最多。 
完全二叉樹(shù)特點(diǎn)：
    葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層；
    最下層的葉子一定集中在左部連續(xù)位置；
    倒數(shù)二層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)部分；
    如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子，集不存在只有右子樹(shù)的情況；
    同樣結(jié)點(diǎn)數(shù)的二叉樹(shù)，完全二叉樹(shù)的深度最小。 

性質(zhì)：

    性質(zhì)1：在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn);
    性質(zhì)2：深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn);
    性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1; 
    性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|log2 n|+1;(|x|為不大于x的最大整數(shù))
    性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)任一結(jié)點(diǎn)i：
            1)如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根；如果i>1，則其雙親是結(jié)點(diǎn)；
            2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子，否則其左孩子是結(jié)點(diǎn)2i； 
            3)如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子是結(jié)點(diǎn)2i+1。

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：完全二叉樹(shù)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

/* 二叉樹(shù)的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義*/ 
/* lchild data rchild */ 
typedef struct BiTNode{             /* 結(jié)點(diǎn)結(jié)構(gòu) */
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

遍歷二叉樹(shù)：
二叉樹(shù)的遍歷(traversing binary tree)
指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪(fǎng)問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被且僅被訪(fǎng)問(wèn)一次 ；

前序遍歷：
若二叉樹(shù)為空，則返回；否則先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再前序遍歷右子樹(shù)；

/* 二叉樹(shù)的前序遍歷遞歸算法 */ 
void PreOrderTraverse(BiTree T){
    if(T == NULL)
        return;
    printf("%c",T->data);
    PreOrderTraverse(T->lchild);
    preOrderTraverse(T->rchild);
}

中序遍歷：
若二叉樹(shù)為空，則返回；否則從根結(jié)點(diǎn)開(kāi)始(注意不是先訪(fǎng)問(wèn)根結(jié)點(diǎn)) ，中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)；

/* 二叉樹(shù)的中序遍歷遞歸算法 */ 
void InOrderTraverse(BiTree T){
    if(T == NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c",T->data);
    InOrderTraverse(T->rchild);
}

后序遍歷：
若二叉樹(shù)為空，則返回；否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪(fǎng)問(wèn)左右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)；

/* 二叉樹(shù)的中序遍歷遞歸算法 */ 
void PostOrderTraverse(BiTree T){
    if(T == NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);
}

層序遍歷：
若二叉樹(shù)為空，則返回；否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪(fǎng)問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)；

建立二叉樹(shù)：

/* 默認(rèn)用戶(hù)按前序遍歷序列輸入二叉樹(shù)數(shù)據(jù)  */ 
/* #表示空樹(shù)，構(gòu)建二叉鏈表來(lái)表示二叉樹(shù)T */
void CreatBiTree(BiTree *T) {
    TElemType ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else{
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(0);
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }       
}

線(xiàn)索二叉樹(shù)(Threaded Binary Tree)
指向前驅(qū)和后繼的指針?lè)Q為線(xiàn)索，加上線(xiàn)索的二叉鏈表稱(chēng)為線(xiàn)索鏈表，相應(yīng)的二叉樹(shù)就稱(chēng)為線(xiàn)索二叉樹(shù)。
lchild ltag data rtag rchild
ltag為0時(shí)，指向該結(jié)點(diǎn)的左孩子，為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)；
rtag為0時(shí)，指向該結(jié)點(diǎn)的右孩子，為1時(shí)指向該結(jié)點(diǎn)的后繼；

線(xiàn)索二叉樹(shù)的結(jié)構(gòu)實(shí)現(xiàn)：

/* 二叉樹(shù)的二叉線(xiàn)索存儲(chǔ)結(jié)構(gòu)定義 */
typedef enum{Link,Thread} PointerTag;   /*Link == 0 表示指向左右孩子指針 */
                                        /*Thread == 0 表示指向前驅(qū)或后繼的線(xiàn)索 */ 
typedef struct BiThrNode{               /*二叉樹(shù)線(xiàn)索存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu) */
    TElemtype data;     
    struct BiThrNode *lchild,*rchild;
    PointerTag LTag;
    PointerTag RTag; 
}BiThrNode,*BiThrTree;

/*中序遍歷進(jìn)行中序線(xiàn)索化 */
BiThrTree pre;
void InThreading(BiThrTree p){
    if(p){
        InThreading(p->lchild);     /*遞歸左子樹(shù)線(xiàn)索化 */
        
        if(!p->lchild){             /*沒(méi)有左孩子 */
            p->LTag=Thread;         /*前驅(qū)線(xiàn)索*/
            p->lchild=pre;          /*左孩子指針指向前驅(qū) */
        }
        
        if(!pre->rchild){           /*前驅(qū)沒(méi)有右孩子 */
            pre->RTag=Thread;       /*后繼線(xiàn)索 */
            pre->rchild=p;          /*前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點(diǎn)p) */
        }
        
        pre=p;                      /*保持pre指向p的前驅(qū) */
        
        InThreading(p->rchild);     /*遞歸右子樹(shù)線(xiàn)索化 */
    }
}

/*中序遍歷二叉線(xiàn)索鏈表表示的二叉樹(shù) */
Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p = T->lchild;
    while( P!= T){
        while( p->LTag == Link){
            p = p->lchild;
                }
            printf("%c",p->data);
        while( p->RTag == Thread && p->rchild != T){
            p = p->rchild;
            printf("%c",p->data);
        }
        p = p->rchild;
    }
    return Ok;
}

實(shí)例：創(chuàng)建一棵線(xiàn)索二叉樹(shù)，并中序遍歷該二叉樹(shù)

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

//  線(xiàn)索存儲(chǔ)標(biāo)志位
//  Link(0)：表示指向左右孩子的指針
//  Thread(1) ：表示指向前驅(qū)后繼的線(xiàn)索
typedef enum {Link,Thread} PointerTag;

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag ltag;
    PointerTag rtag;
} BiThrNode,*BiThrTree;

//  創(chuàng)建一棵二叉樹(shù)，約定用戶(hù)遵照前序遍歷的方式輸入數(shù)據(jù)
void CreatBiThrTree(BiThrTree *T) {
    char c;
    scanf("%c",&c);
    if(' ' == c)
        *T = NULL;
    else {
        *T = (BiThrNode *)malloc(sizeof(BiThrNode));
        (*T)->data = c;
        (*T)->ltag = Link;
        (*T)->rtag = Link;
        CreatBiThrTree(&(*T)->lchild);
        CreatBiThrTree(&(*T)->rchild);
    }
}

//  中序遍歷線(xiàn)索化（遞歸）
BiThrTree pre;  //全局變量，始終指向剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)

void InThreading(BiThrTree T) {
    if(T) {
        InThreading(T->lchild);

        if(!T->lchild) {
            T->ltag = Thread;
            T->lchild = pre;
        }

        if(!pre->rchild) {
            pre->rtag = Thread;
            pre->rchild = T;
        }

        pre = T;

        InThreading(T->rchild);
    }
}

void InOrderThreading(BiThrTree *p,BiThrTree T) {
    *p = (BiThrNode *)malloc(sizeof(BiThrNode));
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->rchild = *p;
    if(!T){
        (*p)->lchild = *p;
    }
    else{
        (*p)->lchild = T;
        pre = *p; 
        InThreading(T);
        pre->rchild = *p;
        pre->rtag = Thread;
        (*p)->rchild = pre; 
    }
}
//  中序遍歷二叉樹(shù)，非遞歸 
void InOrederTraverse(BiThrTree T){
    BiThrTree p;
    p = T->lchild;
    while( p!= T){
        while( p->ltag == Link)
            p = p->lchild;
            
        printf("%c",p->data);
        
        while( p->rtag == Thread && p->rchild != T){
            p = p->rchild;
            printf("%c",p->data);
        }
        
        p = p->rchild;
    }
}

int main(int argc, char *argv[]) {
    BiThrTree p,T = NULL;
    CreatBiThrTree(&T);
    InOrderThreading(&p,T);
    printf("中序遍歷輸出結(jié)果為：");
    InOrederTraverse( p ) ;
    printf("\n");

    return 0;
}

實(shí)例：創(chuàng)建一棵二叉樹(shù)，并分別按前序、中序、后序方式遍歷二叉樹(shù)。

#include <stdio.h>
#include <stdlib.h>

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

//  創(chuàng)建一棵二叉樹(shù) ,約定用戶(hù)遵照前序遍歷的方式輸入數(shù)據(jù)
CreateBiTree(BiTree *T) {
    char c;
    scanf("%c",&c);
    if(' '==c) {
        *T = NULL;
    } else {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

//  前序遍歷二叉樹(shù)
PreOrderTraverse(BiTree T) {
    if( T ) {
        printf("%c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

//  中序遍歷二叉樹(shù)
InOrderTraverse(BiTree T) {
    if( T ) {
        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
}
//  后序遍歷二叉樹(shù)
PostOrderTraverse(BiTree T) {
    if( T ) {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c",T->data);
    }
}

int main(int argc, char *argv[]) {

    printf("建一棵二叉樹(shù) ,約定用戶(hù)遵照前序遍歷的方式輸入數(shù)據(jù)\n");
    BiTree T = NULL;

    CreateBiTree(&T) ;
    printf("\n 前序遍歷結(jié)果是：\n");
    PreOrderTraverse(T);
    printf("\n 中序遍歷結(jié)果是：\n");
    InOrderTraverse(T);
    printf("\n 后序遍歷結(jié)果是：\n");
    PostOrderTraverse(T);
    return 0;
}