二叉樹的定義：

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

二叉樹具有五種基本的形態(tài)：

1. 空二叉樹。
2. 只有一個(gè)根結(jié)點(diǎn)。
3. 根結(jié)點(diǎn)只有左子樹。
4. 根結(jié)點(diǎn)只有右子樹。

特殊的二叉樹

1. 斜樹。
2. 滿二叉樹。
3. 完全二叉樹。

[[222529]]

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

二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲位置，也就是數(shù)組的下標(biāo)要能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系，比如雙親與孩子的關(guān)系，左右兄弟的關(guān)系。

使用順序存儲結(jié)構(gòu)表現(xiàn)二叉樹的時(shí)候，在其線性結(jié)構(gòu)中，會存在一些空結(jié)點(diǎn)，但是其會占據(jù)一定的內(nèi)存空間，會造成存儲空間的浪費(fèi)；所以，順序存儲結(jié)構(gòu)一般只用于完全二叉樹。

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)：

由于二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為每個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域，通常將其稱之為二叉鏈表。

二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義代碼：

typedef char TElemType; 
typedef struct BinaryTreeNode{ 
    TElemType data;     
    //lchild指向左結(jié)點(diǎn)的指針 
    //rchild指向右結(jié)點(diǎn)的指針 
    struct BinaryTreeNode *lchild,*rchild; 
}BinaryTreeNode,*BinaryTree; 

二叉樹的遍歷

二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序一次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。

二叉樹的遍歷方法：

1. 前序遍歷
2. 中序遍歷
3. 后序遍歷

1.首先創(chuàng)建一棵二叉樹

構(gòu)建二叉樹，向結(jié)點(diǎn)的數(shù)據(jù)域中添加字符。

void CreateBinaryTree(BinaryTree *T){ 
    TElemType ch;     
    cin>>ch;     
    if (ch=='$'){ 
        *T=NULL; 
    }else{ 
        *T=new BinaryTreeNode;         
        if (!*T)return; 
        (*T)->data=ch; 
        CreateBinaryTree(&(*T)->lchild); 
        CreateBinaryTree(&(*T)->rchild); 
    } 
} 

2.二叉樹的前序遍歷算法

void PreOrderTraverse(BinaryTree T){     
if (T==NULL){         
    cout<<"#"<<"  ";         
        return; 
    }     
    cout<<T->data<<"  "; 
    PreOrderTraverse(T->lchild); 
    PreOrderTraverse(T->rchild); 
} 

3.二叉樹的中序遍歷算法

void InOderTraverse(BinaryTree T){     
if(T!=NULL){         
        cout<<"#"<<"  ";         
        return; 
    } 
    InOderTraverse(T->lchild);     
    cout<<T->data<<"  "; 
    InOrderTraverse(T->rchild); 
} 

4.二叉樹的后序遍歷算法

void PostOrderTraverse(BinaryTree T){     
    if (T->NULL){         
        cout<<"#"<<"  ";         
        return; 
    } 
    PostOrderTraverse(T->lchild); 
    PostOrderTraverse(T->rchild);     
    cout<<T->data<<"  "; 
} 

前序遍歷、中序遍歷和后序遍歷算法的核心算法大致相同，都是利用了函數(shù)遞歸的原理。這里順帶補(bǔ)充一下關(guān)于函數(shù)遞歸調(diào)用的原理：

裴波那契數(shù)列的實(shí)現(xiàn)來講解函數(shù)的遞歸調(diào)用，假設(shè)存在這樣一個(gè)函數(shù)：

使用遞歸實(shí)現(xiàn)裴波那契數(shù)列代碼如下：

int Fibonacci(int i){     
    if (i<2){         
        return i==0?0:1; 
    }     
        return Fibonacci(i-1)+Fibonacci(i-2); 
} 

通過二叉樹的結(jié)構(gòu)來分析遞歸調(diào)用的執(zhí)行過程：（摘自大話數(shù)據(jù)結(jié)構(gòu) P103頁）

主函數(shù)中的測試代碼如下：

//測試代碼int main() 
{ 
    BinaryTree tree = new BinaryTreeNode;     
    cout << "構(gòu)建一顆由字符構(gòu)成的二叉樹，#代表空" << endl; 
    CreateBinaryTree(&tree);     
    cout << "二叉樹的前序遍歷輸出" << endl; 
    PreOderTraverse(tree);     
    cout << endl;     
    cout << "二叉樹的中序遍歷輸出" << endl; 
    InOderTraverse(tree);     
    cout << endl;     
    cout << "二叉樹的后序遍歷輸出" << endl; 
    PostOderTraverse(tree);     
    cout << endl;     
    return 0; 
} 

輸出如下圖所示：

假設(shè)輸入這樣一個(gè)二叉樹數(shù)據(jù)結(jié)構(gòu)：

代表當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?/strong>