二叉樹的代碼實現

   二叉樹是一種非線性的結構，但是在計算機中存儲時，卻要按照線性來存儲。二叉樹也是由一個一個結點構成，只不過是，一個結點中既要存放數據，又要存放左孩子的指針和右孩子的指針。所以，我們想要實現二叉樹，首先就得有一個二叉樹的結構，根據剛才的分析，那么二叉樹結構中的變量應該要有三個。代碼如下：

struct BiTNode{

    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
};

   有了這么一個二叉樹的結構之后，我們可以開始動態的創建結點。比如，我們要創建的這棵樹有5個元素，A、B、C、D、E。那么，創建結點的代碼如下：

struct BiTNode *A = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *B = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *C = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *D = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *E = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );

接下來，就是要對這些結點進行初始化，并且生成一棵樹。這棵樹，先序遍歷結果為：

A->B->C->D->E

中序遍歷結果為：

B->A->D->C->E

有了樹的理論上的形狀之后，我們要開始對這些結點進行聯接。代碼如下：

A->data = 'A';
A->lchild = B;
A->rchild = C;
B->data = 'B';
B->lchild = B->rchild = NULL;
C->data = 'C';
C->lchild = D;
C->rchild = E;
D->data = 'D';
D->lchild = D->rchild = NULL;
E->data = 'E';
E->lchild = E->rchild = NULL;

二叉樹創建好之后，就是要開始遍歷二叉樹了。二叉樹的遍歷有三種，前序，中序和后序。二叉樹的遍歷事實上是通過遞歸實現的。那么，先來實現，先序遍歷。代碼如下：

void PreOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
    printf ( "%c", T->data );     //先訪問根結點
    if ( T != NULL )
    PreOrderTraverse ( T->lchild );  //訪問左子樹
    if ( T != NULL )
    PreOrderTraverse ( T->rchild );   //訪問右子樹
    
}

接著是中序遍歷，中序遍歷不過是先訪問左子樹，再訪問根結點，最后訪問右子樹。代碼如下：

void InOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
        InOrderTraverse ( T->lchild );
    if ( T != NULL )
        printf ( "%c", T->data );
    if ( T != NULL )
        InOrderTraverse ( T->rchild );

}

最后一種，就是后序遍歷。后序遍歷就是先訪問左子樹，再訪問右子樹，最后訪問根結點。代碼如下：

void PostOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
        PostOrderTraverse ( T->lchild );
    if ( T != NULL )
        PostOrderTraverse ( T->rchild );
    if ( T != NULL )
        printf ( "%c", T->data );

}