樹(Tree)
定義

    樹(Tree) 是n個(n≥0)個結(jié)點的有限集补鼻。n=0時稱為空樹磷杏。
    在任何一個非空樹中：
        (1) 有且僅有一個特定的稱為根(root)的結(jié)點督禽；
        (2) 當n>1時脆霎，其余結(jié)點可分為m個互不相交的有限集。(子樹) 

結(jié)點分類

    結(jié)點擁有的子樹數(shù)稱為結(jié)點的度(Degree)狈惫； 
    度為0的結(jié)點稱為葉結(jié)點(Leaf) 或終端結(jié)點睛蛛；
    度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點；
    除根結(jié)點之外胧谈，分支結(jié)點也稱為內(nèi)部結(jié)點忆肾；
    樹的度是樹內(nèi)各結(jié)點的度的最大值。 

抽象數(shù)據(jù)類型

ADT 樹(tree) 
Data 
    樹是由一個根結(jié)點和若干棵子樹構(gòu)成菱肖。數(shù)中結(jié)點具有相同的數(shù)據(jù)類型和層次關(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

樹的存儲結(jié)構(gòu)

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

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

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

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

每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點蔑滓。(多重鏈表表示法)造成浪費

孩子表示法：把每個結(jié)點的孩子結(jié)點排列起來郊酒，以單鏈表作存儲結(jié)構(gòu)。則n個孩子有n個孩子鏈表键袱。
如果是葉子結(jié)點則此單鏈表為空燎窘，然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)蹄咖，存放進一個一維數(shù)組褐健。

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

孩子兄弟表示法：任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的澜汤，它的右兄弟如果存在也是唯一的蚜迅。
因此，設(shè)置兩個指針俊抵，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟谁不。

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

二叉樹(Binary Tree)
是n個結(jié)點的有限集合，該集合或者為空集徽诲，或者由一個根結(jié)點和兩棵互不相交的刹帕，分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。

特點：

滿二叉樹：   
    在一棵二叉樹中谎替，如果所有分支結(jié)點都存在左子樹和右子樹偷溺，并且所有葉子都在同一層上，這樣的樹叫~钱贯；
完全二叉樹：
    對一棵具有n個結(jié)點的二叉樹按層序編號挫掏，如果編號為i的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹秩命。

滿二叉樹一定是一棵完全二叉樹尉共，但是完全二叉樹不一定是滿的。

滿二叉樹特點：
    葉子只能出現(xiàn)在最下一層硫麻；
    非葉子結(jié)點的度一定是2爸邢；
    在同樣深度的二叉樹中，滿二叉樹的結(jié)點個數(shù)最多拿愧，葉子數(shù)最多杠河。 
完全二叉樹特點：
    葉子結(jié)點只能出現(xiàn)在最下兩層；
    最下層的葉子一定集中在左部連續(xù)位置浇辜；
    倒數(shù)二層券敌，若有葉子結(jié)點，一定都在右部連續(xù)部分柳洋；
    如果結(jié)點度為1待诅，則該結(jié)點只有左孩子，集不存在只有右子樹的情況熊镣；
    同樣結(jié)點數(shù)的二叉樹卑雁，完全二叉樹的深度最小募书。 

性質(zhì)：

    性質(zhì)1：在二叉樹的第i層上至多有2^(i-1)個結(jié)點;
    性質(zhì)2：深度為k的二叉樹至多有2^k-1個結(jié)點;
    性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0测蹲，度為2的結(jié)點數(shù)為n2莹捡，則n0=n2+1; 
    性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為|log2 n|+1;(|x|為不大于x的最大整數(shù))
    性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹，對任一結(jié)點i：
            1)如果i=1扣甲，則結(jié)點i是二叉樹的根篮赢；如果i>1，則其雙親是結(jié)點琉挖；
            2)如果2i>n启泣，則結(jié)點i無左孩子，否則其左孩子是結(jié)點2i示辈； 
            3)如果2i+1>n,則結(jié)點i無右孩子寥茫，否則其右孩子是結(jié)點2i+1。

二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)：完全二叉樹
鏈式存儲結(jié)構(gòu)：

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

遍歷二叉樹：
二叉樹的遍歷(traversing binary tree)
指從根結(jié)點出發(fā)矾麻，按照某種次序依次訪問二叉樹中所有結(jié)點坠敷，使得每個結(jié)點被且僅被訪問一次 ；

前序遍歷：
若二叉樹為空射富，則返回膝迎；否則先訪問根結(jié)點，然后前序遍歷左子樹胰耗，再前序遍歷右子樹限次；

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

中序遍歷：
若二叉樹為空，則返回柴灯；否則從根結(jié)點開始(注意不是先訪問根結(jié)點) 卖漫，中序遍歷根結(jié)點的左子樹，然后訪問根結(jié)點赠群，最后中序遍歷右子樹羊始；

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

后序遍歷：
若二叉樹為空，則返回查描；否則從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹突委，最后訪問根結(jié)點；

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

層序遍歷：
若二叉樹為空冬三，則返回匀油；否則從樹的第一層，也就是根結(jié)點開始訪問勾笆，從上而下逐層遍歷敌蚜，在同一層中，按從左到右的順序?qū)Y(jié)點逐個訪問窝爪；

建立二叉樹：

/* 默認用戶按前序遍歷序列輸入二叉樹數(shù)據(jù)  */ 
/* #表示空樹弛车，構(gòu)建二叉鏈表來表示二叉樹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);
    }       
}

線索二叉樹(Threaded Binary Tree)
指向前驅(qū)和后繼的指針稱為線索齐媒，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹纷跛。
lchild ltag data rtag rchild
ltag為0時里初，指向該結(jié)點的左孩子，為1時指向該結(jié)點的前驅(qū)忽舟；
rtag為0時，指向該結(jié)點的右孩子淮阐，為1時指向該結(jié)點的后繼叮阅；

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

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

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

/*中序遍歷二叉線索鏈表表示的二叉樹 */
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;
}

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

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

typedef char ElemType;

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

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

//  創(chuàng)建一棵二叉樹泣特，約定用戶遵照前序遍歷的方式輸入數(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);
    }
}

//  中序遍歷線索化（遞歸）
BiThrTree pre;  //全局變量浩姥，始終指向剛剛訪問過的結(jié)點

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; 
    }
}
//  中序遍歷二叉樹，非遞歸 
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;
}

實例：創(chuàng)建一棵二叉樹状您，并分別按前序勒叠、中序、后序方式遍歷二叉樹膏孟。

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

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

//  創(chuàng)建一棵二叉樹 ,約定用戶遵照前序遍歷的方式輸入數(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);
    }
}

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

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

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

    printf("建一棵二叉樹 ,約定用戶遵照前序遍歷的方式輸入數(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;
}