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

     操作，這樣就存在一個(gè)操作順序問(wèn)題，由此提出了二叉樹(shù)的遍歷操作。所謂遍歷二叉樹(shù)就  

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

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

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

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

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

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

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

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

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

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

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

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

（1）先序遍歷

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

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

先序遍歷左子樹(shù)；

先序遍歷右子樹(shù)。

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

中序遍歷左子樹(shù)；

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

中序遍歷右子樹(shù)。

（3）后序遍歷

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

后序遍歷左子樹(shù)；

后序遍歷右子樹(shù)；

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

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

二叉樹(shù)的兩種遍歷方法：

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

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

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

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

這條包線對(duì)于理解二叉樹(shù)的遍歷過(guò)程很有用。

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

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

過(guò)程，因此，這三種遍歷操作的算法可以用遞歸函數(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ù)

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

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

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

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

訪問(wèn)過(guò)程描述如下：

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

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

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

若它有右孩子，則訪問(wèn)右孩子，并記錄下來(lái)。

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

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

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

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

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

若其有左孩子，則訪問(wèn)左孩子，并將其左孩子入隊(duì)；

若其有右孩子，則訪問(wèn)右孩子，并將其右孩子入隊(duì)；

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

   五、典型二叉樹(shù)的操作算法

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

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

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

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

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

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

算法：

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

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

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

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

算法：

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

   3、 交換二叉樹(shù)的左右子樹(shù)

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

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

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

算法：

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

   4 、求二叉樹(shù)的高度

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

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

算法：

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

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

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

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

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

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

這兩個(gè)指針看作是二叉樹(shù)中的左孩子指針和孩子右指針時(shí)，就是一棵二叉樹(shù)了。

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

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

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

    2 、二叉樹(shù)還原成樹(shù)或森林

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

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

走，直到為空，途經(jīng)的結(jié)點(diǎn)個(gè)數(shù)是相應(yīng)森林所含樹(shù)的棵數(shù)；若某個(gè)結(jié)點(diǎn)的左指針?lè)强眨f(shuō)明這

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

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