中序線索二叉樹的建立、線索化和周遊

【問題描述】建立一棵二叉樹，接着中序線索化該二叉樹，然後編寫相應函數周遊該中序線索二叉樹

【編碼要求】線索二叉樹周遊過程中不能使用遞歸、不能使用棧。

【輸入形式】二叉樹拓展的前序周遊序列

【輸出形式】中序周遊序列

【樣例輸入】AB#D##CE###

【樣例輸出】BDAEC

審題：

題目一共有三個小問：

1.建立一顆二叉樹。

2.中序線索化該二叉樹。

3.基于設定好的線索，中序周遊該二叉樹。

那麼下面，我們逐個擊破這些問題。

首先，建立一顆二叉樹。

以一個結構體封裝好一個線索二叉樹的一個結點所需要的全部屬性：

我這裡用c++的class封裝，因為構造函數挺好用的。

lf和rt分别指向左右孩子，或者，在中序序列裡的前驅（左）和後繼（右）。Ltag和Rtag就是标記lf和rt指向的到底是孩子結點還是線索，如果Ltag為1，說明此時lf指向的是中序序列裡的前驅；如果為0，說明此時，存在左孩子，且lf指向的是左孩子。

class BiNode
{
public:
    BiNode *lf,*rt;
    int Ltag,Rtag;
    Elemtype data;
    BiNode():lf(NULL),rt(NULL),Ltag(0),Rtag(0){}
};
           

然後，用一個class封裝二叉樹對象，暫時隻封裝一個基本屬性根節點指針：

class Bitree
{
public:
    BiNode *root;
    Bitree():root(NULL){}
    BiNode* create(char *str,int &i);
    void print(BiNode *p);
    void inthread(BiNode *p,BiNode **pre);//線索化
    void printByThread();
};
           

create函數就是建立二叉樹的函數。

現在基于鍵盤輸入的前序周遊序列，建立二叉樹。

此處函數接收的兩個參數分别指的是前序周遊序列的字元串和目前通路字元的下标（傳引用是為了把i當成一個全局變量來用）。

預設是生成一個新的結點，然後将新節點設定好之後傳回。

設定的抽象過程就是先把str[i]賦給新節點的data域，再建立左子樹和右子樹。

注意此處，隻有建立左子樹的時候對i進行了+1的操作，而右子樹不用。為什麼呢？因為在建立過程中，一定是先建立左子樹，再建立右子樹，而什麼時候左子樹停止建立呢？那麼就是掃描到‘#’這個字元的時候，這種情況下我對i做了+1處理，是以右子樹不傳++i。當然，你也可以選擇把‘#’處的i++删掉，在建立右子樹的時候傳入++i，也是一樣的。

BiNode* Bitree::create(char *str,int &i)
{
    if(str[i]=='#')
    {
        i++;
        return NULL;
    }
    BiNode *t=new BiNode;
    t->data=str[i];
    t->lf=create(str,++i);
    t->rt=create(str,i);
    return t;
}
           

建立好了一顆未線索化的二叉樹之後，就該進入下一個環節，中序線索化該二叉樹。

所謂中序線索化，說的通俗一點就是，利用那些沒有指向孩子結點的lf和rt，存放中序周遊序列中的前驅和後繼。

既然是中序，那麼代碼基本的結構還是和中序遞歸周遊一樣。

隻不過有兩樣東西不同，一個是函數參數多了一個**pre（二級指針的用意同樣還是把pre當作全局變量來用，因為前驅！=上一個經過的結點），pre指向的是上一個被操作的結點，也就是前驅；另一個是把通路目前結點變成了中間的一大坨加線索的操作，其實加線索也算是一種廣義上的通路吧。

在第一個if語句塊中，如果p->lf==NULL為真，就意味着p沒有左孩子，也就意味着你要加前驅的線索了，那麼pre指向的就是前驅，把它賦給p->lf；因為傳的是二級指針，是以對pre做一個*的操作，再把Ltag置為1。

在第二個if語句塊中，如果*pre!=NULL&&(*pre)->rt==NULL成立，就意味着在序列裡，p->data存在前驅，并且p沒有右孩子。這時候又該你加後繼線索了！不過此處，你并不是對目前結點加後繼線索，而是對pre，也就是對p的前驅結點加後繼線索，為什麼呢？因為程式走到這的時候壓根不知道p的後繼是誰，但它一定能夠知道pre的後繼是p。

做完前驅和後繼的加線索操作之後，把pre的值更新一下

//中序線索化
void Bitree::inthread(BiNode *p,BiNode **pre)
{
    if(p!=NULL)
    {
        //左
        inthread(p->lf,pre);
        
        //中
        if(p->lf==NULL)
        {
            p->lf=*pre;
            p->Ltag=1;
        }
        if(*pre!=NULL&&(*pre)->rt==NULL)
        {
            (*pre)->rt=p;
            (*pre)->Rtag=1;
        }
        (*pre)=p;//可能存在一個節點的前驅有右孩子，是以這句話應該寫在兩個if的外面，比如根節點
        
        //右
        inthread(p->rt,pre);
    }
}
           

中序線索化的工作完成之後，就要解決基于線索周遊二叉樹的問題了。

首先，周遊操作大緻分為兩個步驟，第一個是找到中序周遊序列裡第一個被通路的結點，第二個是，根據線索通路剩下的結點。

為什麼要先找第一個結點的位置呢？因為沒有線索指向它。

找到第一個結點位置非常簡單，那就是一直向左下方搜，找到第一個Ltag為1的點。Ltag為1就代表的是這個結點沒有左孩子，在正常遞歸的中序周遊裡面，也是最先輸出最左下方的結點。

事實上，雖然第一個結點的Ltag為1，但是它的lf的值還是NULL，因為它沒有前驅。

接着，就開始根據線索周遊二叉樹。在循環裡做的第一件事是輸出p指向的data，因為p始終是被移到了下一個待輸出的位置。第二件事是把p移向它的後繼結點，這個時候就要分兩種情況讨論：

1.p的rt指向後繼結點

2.p的rt指向右孩子

在情況1下，找後繼節點非常簡單，因為rt指向的就是後繼結點。

在情況2下，就要根據中序周遊的特性來思考，因為通路的順序總是左中右的，是以，後繼永遠是在p的右子樹中的最左下方的結點，根據這一特點，先把p移向p的右孩子，再一直向下，尋找第一個Ltag為1的結點，這和上面的提到的找到第一個結點的操作相通。

當然，如果p->rt==NULL，那麼證明，p沒有後繼也沒有右孩子，是以周遊完成，可以return了。

void Bitree::printByThread()
{
    BiNode *p=root;
    while(p->Ltag==0)//找到第一個被周遊的結點
    {
        p=p->lf;
    }
    while(1)
    {
        cout<<p->data;//通路節點

        if(p->Rtag==1)//指針移向後繼
        {
            p=p->rt;
        }
        else
        {
            if(p->rt==NULL)
                return;
            else
                for(p=p->rt;p->Ltag==0;p=p->lf);//找到右子樹中的最左端
        }
    }
}
           

以上，三個問題已全部解決，附上完整代碼。

#include <iostream>
#define N 100
#define Elemtype char
using namespace std;

class BiNode
{
public:
    BiNode *lf,*rt;
    int Ltag,Rtag;
    Elemtype data;
    BiNode():lf(NULL),rt(NULL),Ltag(0),Rtag(0){}
};

class Bitree
{
public:
    BiNode *root;
    Bitree():root(NULL){}
    BiNode* create(char *str,int &i);
    void print(BiNode *p);
    void inthread(BiNode *p,BiNode **pre);//線索化
    void printByThread();
};

BiNode* Bitree::create(char *str,int &i)
{
    if(str[i]=='#')
    {
        i++;
        return NULL;
    }
    BiNode *t=new BiNode;
    t->data=str[i];
    t->lf=create(str,++i);
    t->rt=create(str,i);
    return t;
}

void Bitree::print(BiNode *p)
{
    if(p!=NULL)
    {
        cout<<p->data;
        print(p->lf);
        print(p->rt);
    }
}

//中序線索化
void Bitree::inthread(BiNode *p,BiNode **pre)
{
    if(p!=NULL)
    {
        inthread(p->lf,pre);
        if(p->lf==NULL)
        {
            p->lf=*pre;
            p->Ltag=1;
        }
        if(*pre!=NULL&&(*pre)->rt==NULL)
        {
            (*pre)->rt=p;
            (*pre)->Rtag=1;
        }
        (*pre)=p;//可能存在一個節點的前驅有右孩子，是以這句話應該寫在兩個if的外面
        inthread(p->rt,pre);
    }
}

void Bitree::printByThread()
{
    BiNode *p=root;
    while(p->Ltag==0)//找到第一個被周遊的結點
    {
        p=p->lf;
    }
    while(1)
    {
        cout<<p->data;//通路節點

        if(p->Rtag==1)//指針移向後繼
        {
            p=p->rt;
        }
        else
        {
            if(p->rt==NULL)
                return;
            else
                for(p=p->rt;p->Ltag==0;p=p->lf);//找到右子樹中的最左端
        }
    }
}

int main()
{
    char str[N];
    cin>>str;
    Bitree bt;
    int i=0;
    bt.root=bt.create(str,i);
    //bt.print(bt.root);
    BiNode *pre=NULL;
    bt.inthread(bt.root,&pre);
    bt.printByThread();
    return 0;
}