二叉樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在對它進(jìn)行操作時，總是需要逐一對每個數(shù)據(jù)元素實(shí)施

     操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就  

     是按某種順序訪問二叉樹中的每個結(jié)點(diǎn)一次且僅一次的過程。這里的訪問可以是輸出、比

     較、更新、查看元素內(nèi)容等等各種操作。

     二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進(jìn)行訪問；另一類按

     層次訪問。下面我們將分別進(jìn)行討論。

    1、 按根、左子樹和右子樹三部分進(jìn)行遍歷

遍歷二叉樹的順序存在下面6種可能：

    TLR（根左右）, TRL（根右左）

    LTR（左根右）, RTL（右根左）

    LRT（左右根）, RLT（右左根）

     其中，TRL、RTL和RLT三種順序在左右子樹之間均是先右子樹后左子樹，這與人們先左后右

的習(xí)慣不同，因此，往往不予采用。余下的三種順序TLR、LTR和LRT根據(jù)根訪問的位置不同分別

被稱為先序遍歷、中序遍歷和后序遍歷。

（1）先序遍歷

若二叉樹為空，則結(jié)束遍歷操作；否則

訪問根結(jié)點(diǎn)；

先序遍歷左子樹；

先序遍歷右子樹。

（2）中序遍歷若二叉樹為空，則結(jié)束遍歷操作；否則

中序遍歷左子樹；

訪問根結(jié)點(diǎn)；

中序遍歷右子樹。

（3）后序遍歷

若二叉樹為空，則結(jié)束遍歷操作；否則

后序遍歷左子樹；

后序遍歷右子樹；

訪問根結(jié)點(diǎn)。

例如。以下是一棵二叉樹及其經(jīng)過三種遍歷所得到的相應(yīng)遍歷序列

二叉樹的兩種遍歷方法：

（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴(yán)格地按左子樹的所有結(jié)點(diǎn)位于根結(jié)點(diǎn)的左

側(cè)，右子樹的所有結(jié)點(diǎn)位于根右側(cè)的形式繪制，就可以對每個結(jié)點(diǎn)做一條垂線，映射到下面的

水平線上，由此得到的順序就是該二叉樹的中序遍歷序列

（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，

這條包線對于理解二叉樹的遍歷過程很有用。

     由此可以看出：（1）遍歷操作實(shí)際上是將非線性結(jié)構(gòu)線性化的過程，其結(jié)果為線性序列，

并根據(jù)采用的遍歷順序分別稱為先序序列、中序序列或后序序列；（2）遍歷操作是一個遞歸的

過程，因此，這三種遍歷操作的算法可以用遞歸函數(shù)實(shí)現(xiàn)。

（1）先序遍歷遞歸算法
void PreOrder(BTree BT) {
      if (BT) { Visit(BT);
      PreOrder(BT->Lchild);
      PreOrder(BT->Rchild);
}

（2）中序遍歷遞歸算法
void InOrder(BTree BT) {
      if (BT) {
         InOrder(BT->Lchild);
         Visit(BT);
         InOrder(BT->Rchild);
       }
    }

（3）后序遍歷遞歸算法
void PostOrder(BTree BT) {
     if (BT) {
        PostOrder(BT->Lchild);
        PostOrder(BT->Rchild);
        Visit(BT);
       }
    }

   2 、按層次遍歷二叉樹

     實(shí)現(xiàn)方法為從上層到下層，每層中從左側(cè)到右側(cè)依次訪問每個結(jié)點(diǎn)。下面我們將給出一棵

二叉樹及其按層次順序訪問其中每個結(jié)點(diǎn)的遍歷序列。

void LevelOreder(QBTree BT) {
     for (i=1;i<=BT.n;i++)
     if (BT.elem[i]!='#') Visite(BT.elem[i]);
}

二叉樹用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示時，按層遍歷的算法實(shí)現(xiàn)

訪問過程描述如下：

訪問根結(jié)點(diǎn)，并將該結(jié)點(diǎn)記錄下來；

若記錄的所有結(jié)點(diǎn)都已處理完畢，則結(jié)束遍歷操作；否則重復(fù)下列操作。

取出記錄中第一個還沒有訪問孩子的結(jié)點(diǎn)，若它有左孩子，則訪問左孩子，并將記錄下來；

若它有右孩子，則訪問右孩子，并記錄下來。

     在這個算法中，應(yīng)使用一個隊列結(jié)構(gòu)完成這項操作。所謂記錄訪問結(jié)點(diǎn)就是入隊操作；

     而取出記錄的結(jié)點(diǎn)就是出隊操作。這樣一來，我們的算法就可以描述成下列形式：

（1）訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊；

（2）當(dāng)隊列不空時，重復(fù)下列操作：

從隊列退出一個結(jié)點(diǎn)；

若其有左孩子，則訪問左孩子，并將其左孩子入隊；

若其有右孩子，則訪問右孩子，并將其右孩子入隊；

void LevelOrder(BTree *BT) {
      if (!BT) exit;
      InitQueue(Q); p=BT; //初始化
      Visite(p); EnQueue(&Q,p); //訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊
      while (!QueueEmpty(Q)) { //當(dāng)隊非空時重復(fù)執(zhí)行下列操作
      DeQueue(&Q,&p); //出隊
      if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //處理左孩子
      if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //處理右孩子
   }
}

   五、典型二叉樹的操作算法

     1、 輸入一個二叉樹的先序序列，構(gòu)造這棵二叉樹

     為了保證唯一地構(gòu)造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉

    樹的位置上填補(bǔ)一個特殊的字符，比如，'#'。在算法中，需要對每個輸入的字符進(jìn)行判

    斷，如果對應(yīng)的字符是'#'，則在相應(yīng)的位置上構(gòu)造一棵空二叉樹；否則，創(chuàng)建一個新結(jié)

    點(diǎn)。整個算法結(jié)構(gòu)以先序遍歷遞歸算法為基礎(chǔ)，二叉樹中結(jié)點(diǎn)之間的指針連接是通過指針

    參數(shù)在遞歸調(diào)用返回時完成。

算法：

BTree Pre_Create_BT( ) {
      getch(ch);
      if (ch=='#') return NULL;                     //構(gòu)造空樹
      else { BT=(BTree)malloc(sizeof(BTLinklist)); //構(gòu)造新結(jié)點(diǎn)
      BT->data=ch;
      BT->lchild =Pre_Create_BT( );                 //構(gòu)造左子樹
      BT->rchild =Pre_Create_BT( );                 //構(gòu)造右子樹
      return BT;
    }
}

   2、 計算一棵二叉樹的葉子結(jié)點(diǎn)數(shù)目

     這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成判斷該結(jié)點(diǎn)是否

     為葉子結(jié)點(diǎn)，如果是葉子結(jié)點(diǎn)將累加器加1即可。下面這個算法是利用中序遍歷實(shí)現(xiàn)的。

算法：

void Leaf(BTree BT,int *count) {
      if (BT) {
      Leaf(BT->child,&count); //計算左子樹的葉子結(jié)點(diǎn)個數(shù)
      if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
      Leaf(BT->rchild,&count); //計算右子樹的葉子結(jié)點(diǎn)個數(shù)
    }
}

   3、 交換二叉樹的左右子樹

     許多操作可以利用三種遍歷順序的任何一種，只是某種遍歷順序?qū)崿F(xiàn)起來更加方便一  

些。而有些操作則不然，它只能使用其中的一種或兩種遍歷順序。將二叉樹中所有結(jié)點(diǎn)的左右

子樹進(jìn)行交換這個操作就屬于這類情況。

算法：

void change_left_right(BTree BT) {
      if (BT) {
         change_left_right(BT->lchild);
         change_left_right(BT->rchild);
         BT->lchild<->BT->rchild;
       }
   }

   4 、求二叉樹的高度

     這個操作使用后序遍歷比較符合人們求解二叉樹高度的思維方式。首先分別求出左右子樹

的高度，在此基礎(chǔ)上得出該棵樹的高度，即左右子樹較大的高度值加1。

算法：

int hight(BTree BT) {     //h1和h2分別是以BT為根的左右子樹的高度
     if (BT==NULL) return 0;
     else {
         h1=hight(BT->lchild);
         h2=hight(BT->right);
         return max{h1,h2}+1;
        }
   }

   六、樹、森林與二叉樹的轉(zhuǎn)換

   1、 樹、森林轉(zhuǎn)換成二叉樹

     將一棵樹轉(zhuǎn)換成二叉樹的方法：

     將一棵樹轉(zhuǎn)換成二叉樹實(shí)際上就是將這棵樹用孩子兄弟表示法存儲即可，此時，樹中的每

個結(jié)點(diǎn)最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側(cè)第一個兄弟。當(dāng)你將

這兩個指針看作是二叉樹中的左孩子指針和孩子右指針時，就是一棵二叉樹了。

     特點(diǎn)：一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有右孩子。

     將森林轉(zhuǎn)換成二叉樹的方法與一棵樹轉(zhuǎn)換成二叉樹的方法類似，只是把森林中所有樹的根

      結(jié)點(diǎn)看作兄弟關(guān)系，并對其中的每棵樹依依地進(jìn)行轉(zhuǎn)換。

    2 、二叉樹還原成樹或森林

     這個過程實(shí)際上是樹、森林轉(zhuǎn)換成二叉樹的逆過程，即將該二叉樹看作是樹或森林的孩子

兄弟表示法。比如，若二叉樹為空，樹也為空；否則，由二叉樹的根結(jié)點(diǎn)開始，延右指針向下

走，直到為空，途經(jīng)的結(jié)點(diǎn)個數(shù)是相應(yīng)森林所含樹的棵數(shù)；若某個結(jié)點(diǎn)的左指針非空，說明這

個結(jié)點(diǎn)在樹中必有孩子，并且從二叉樹中該結(jié)點(diǎn)左指針?biāo)附Y(jié)點(diǎn)開始，延右指針向下走，直到

為空，途經(jīng)的結(jié)點(diǎn)個數(shù)就是這個結(jié)點(diǎn)的孩子數(shù)目。