樹之二叉樹

       本文來介紹二叉樹。二叉樹是樹形結構的一個重要類型，其重要性不言而喻，我們還會在後面經常應用到二叉樹。比如說樹、森林二叉樹之間可互相轉換，對樹和森林的操作可對應為對相應二叉樹的操作。

       本文介紹的二叉樹具有鍊式存儲結構，其存儲結構為二叉連結清單（當然也有三叉連結清單的存儲結構）。本文介紹了二叉樹的各種周遊與二叉樹的一些其他操作。

       二叉樹的周遊操作是二叉樹其他操作的基礎。不同的周遊并非重複，而是具有實際的意義，即不同的問題會應用不同的周遊操作。比如說判斷倆個二叉樹是否相等，用先序周遊比較好；删除一個二叉樹，用後序周遊比較好等等。

#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;

typedef char Datatype;          //資料域中資料的類型
typedef struct node{            //結點類型
    Datatype data;              //資料域
    struct node *lchild,*rchild;//左右孩子指針
}BinTNode;
typedef BinTNode *BinTree;      //BinTree為指向BinTNode類型結點的指針類型

//***********************二叉樹的周遊************************

void PreOrder(BinTree T){
    //先序周遊遞歸算法
    if(T){
        printf("%c",T->data);//先通路根節點
        PreOrder(T->lchild); //再通路左子樹
        PreOrder(T->rchild); //最後通路右子樹
    }
}

void InOrder(BinTree T){
    //中序周遊遞歸算法
    if(T){                   // 如果二叉樹非空
        InOrder(T->lchild);  //先通路左子樹
        printf("%c",T->data);//再通路根結點
        InOrder(T->rchild);  //最後通路右子樹
    }
}

void PostOrder(BinTree T){
    //後序周遊遞歸算法
    if(T){
        PostOrder(T->lchild);//先通路左子樹
        PostOrder(T->rchild);//再通路右子樹
        printf("%c",T->data);//最後通路根結點
    }
}

void LevelOrder(BinTree T){
    //層次周遊算法,按照從左到右,從上到下的順序周遊二叉樹
    BinTNode *p=T;            //工作指針初始化為根指針
    queue<BinTNode*>q;        //隊列中元素的類型是指向根節點的指針
    while(p){                 //當隊列中的元素不是空指針時進入循環
        printf("%c",p->data); //通路目前結點的資料域
        if(p->lchild)         //如果左子樹不為空,則将左指針進隊列
            q.push(p->lchild);
        if(p->rchild)         //如果右子樹不空,則将右指針進隊列
            q.push(p->rchild);
        if(q.empty())         //如果隊列為空,則退出循環
            break;
        p=q.front();          //取隊頭元素
        q.pop();              //彈出隊頭元素
    }
}

void InOrder1(BinTree T){
    //中序周遊二叉樹的非遞歸算法
    stack<BinTNode*>s;       //棧的元素時指向樹結點的指針
    BinTNode *p=T;           //活動指針初始化為根指針
    while(p||!s.empty()){    //進入循環的條件:要麼子樹不空,要麼棧不空
        if(p){               //根指針進棧,周遊左子樹
            s.push(p);
            p=p->lchild;
        }
        else{                //根指針退棧,通路根節點,周遊右子樹
            p=s.top();
            s.pop();
            printf("%c",p->data);
            p=p->rchild;
        }
    }
}

//***************二叉樹的一些其他操作******************

void CreateBinTree(BinTree *T){
    //二叉連結清單的構造
    //基于先序周遊的構造,先序序列中虛結點表示空指針的位置
    //T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
    char ch;
    ch=getchar();
    if(ch==' ')
        *T=NULL;//讀入空格，将相應指針置空
    else{
        *T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點
        (*T)->data=ch;//給結點的資料域指派
        CreateBinTree(&(*T)->lchild);//構造左子樹
        CreateBinTree(&(*T)->rchild);//構造右子樹
    }
}

//***********************測試函數************************

int main(){
    BinTree T;
    printf("輸入字元串（空格字元表示空樹），來建立二叉樹！\n");
    CreateBinTree(&T);
    printf("二叉樹已經建好，先序周遊序列為：\n");
    PreOrder(T);
    printf("\n中序周遊序列為(遞歸)：\n");
    InOrder(T);
    printf("\n中序周遊序列為(非遞歸)：\n");
    InOrder1(T);
    printf("\n後序周遊序列為：\n");
    PostOrder(T);
    printf("\n層次周遊序列為：\n");
    LevelOrder(T);
    return 0;
}
           

在下圖中的測試樣例中，建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮，其中∮表示空樹，那麼如圖所示的二叉樹的先序周遊序列為：A B D C E F，中序周遊序列為：D B A E C F，後序周遊序列為：D B E F C A。

測試樣例：