二叉樹是一種非線性的數據結構，在對它進行操作時，總是需要逐一對每個數據元素實施

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

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

     較、更新、查看元素內容等等各種操作。

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

     層次訪問。下面我們將分別進行討論。

    1、 按根、左子樹和右子樹三部分進行遍歷

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

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

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

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

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

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

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

（1）先序遍歷

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

訪問根結點；

先序遍歷左子樹；

先序遍歷右子樹。

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

中序遍歷左子樹；

訪問根結點；

中序遍歷右子樹。

（3）后序遍歷

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

后序遍歷左子樹；

后序遍歷右子樹；

訪問根結點。

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

二叉樹的兩種遍歷方法：

（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴格地按左子樹的所有結點位于根結點的左

側，右子樹的所有結點位于根右側的形式繪制，就可以對每個結點做一條垂線，映射到下面的

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

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

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

     由此可以看出：（1）遍歷操作實際上是將非線性結構線性化的過程，其結果為線性序列，

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

過程，因此，這三種遍歷操作的算法可以用遞歸函數實現。

（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 、按層次遍歷二叉樹

     實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵

二叉樹及其按層次順序訪問其中每個結點的遍歷序列。

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

二叉樹用鏈式存儲結構表示時，按層遍歷的算法實現

訪問過程描述如下：

訪問根結點，并將該結點記錄下來；

若記錄的所有結點都已處理完畢，則結束遍歷操作；否則重復下列操作。

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

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

     在這個算法中，應使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作；

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

（1）訪問根結點，并將根結點入隊；

（2）當隊列不空時，重復下列操作：

從隊列退出一個結點；

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

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

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

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

     1、 輸入一個二叉樹的先序序列，構造這棵二叉樹

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

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

    斷，如果對應的字符是'#'，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結

    點。整個算法結構以先序遍歷遞歸算法為基礎，二叉樹中結點之間的指針連接是通過指針

    參數在遞歸調用返回時完成。

算法：

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

   2、 計算一棵二叉樹的葉子結點數目

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

     為葉子結點，如果是葉子結點將累加器加1即可。下面這個算法是利用中序遍歷實現的。

算法：

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

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

     許多操作可以利用三種遍歷順序的任何一種，只是某種遍歷順序實現起來更加方便一  

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

子樹進行交換這個操作就屬于這類情況。

算法：

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

   4 、求二叉樹的高度

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

的高度，在此基礎上得出該棵樹的高度，即左右子樹較大的高度值加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;
        }
   }

   六、樹、森林與二叉樹的轉換

   1、 樹、森林轉換成二叉樹

     將一棵樹轉換成二叉樹的方法：

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

個結點最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側第一個兄弟。當你將

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

     特點：一棵樹轉換成二叉樹后，根結點沒有右孩子。

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

      結點看作兄弟關系，并對其中的每棵樹依依地進行轉換。

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

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

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

走，直到為空，途經的結點個數是相應森林所含樹的棵數；若某個結點的左指針非空，說明這

個結點在樹中必有孩子，并且從二叉樹中該結點左指針所指結點開始，延右指針向下走，直到

為空，途經的結點個數就是這個結點的孩子數目。