二叉樹的基本操作(先序序列建立二叉樹/先序周遊遞歸算法/中序周遊遞歸算法/後序周遊遞歸算法/求二叉樹深度的遞歸算法)

      二叉樹的存儲結構有順序存儲和鍊式存儲兩種存儲方式，這裡我們采用使用頻率較高的鍊式存儲方式(二叉連結清單)來存儲二叉樹.

      下面給出二叉樹結點的定義.

struct BiTreeNode//二叉樹結點定義
{
    BiTreeNode* LChild;//左孩子指針域
    int data;
    BiTreeNode* RChild;//右孩子指針域
};
           

      在上面的定義中，LChild指針指向該結點的左孩子結點，RChild指針指向該結點的右孩子結點，另外data變量存儲該結點的資料資訊. 值得一提的是，由于二叉樹的某個結點對應的後繼可能有兩個(而不是至多隻有一個)，故二叉樹這種結構是非線性結構，其操作難度要明顯大于線性結構(比如順序表、單連結清單). 

      有了二叉樹結點的定義，我們再來分析該如何在主存中建立一棵二叉樹.

      下面給出以先序周遊序列建立二叉樹的具體過程.

void CreateBiTree(BiTreeNode* &T)//以先序序列建立二叉樹
{
    char ch;
    cin>>ch;
    if(ch!='#')
    {
        T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
        T->data=ch;
        CreateBiTree(T->LChild);
        CreateBiTree(T->RChild);
    }
    else
    {
        T=NULL;
    }
}
           

        在上述過程中，我們可以發現，當輸入的字元為‘#’時, 建立空樹，否則建立一個"實在"的結點. 之後再遞歸建立該結點的左孩子結點和右孩子結點. 從上述算法的書寫過程中我們可以清晰地看出，這是一個遞歸算法：相信很多朋友和我之前一樣，一提到遞歸算法就會感到"頭大"——其實這是畏難情緒在作怪罷了. 當你初步掌握遞歸算法的設計套路後, 你會發現其實遞歸算法是比較容易寫出的. 

        已掌握二叉樹先序周遊遞歸算法的朋友可以對比這兩種算法的結構，對比後應該能發現，其實它們在結構上是一回事. 

        為此，下面給出先序周遊二叉樹的遞歸算法. 

void InOrderTraverse(BiTreeNode* &T)//先序周遊通路二叉樹
{
    if(T!=NULL)
    {
        putchar(T->data);//在螢幕上顯示字元, 若直接用cout<<T->data, 則輸出的字元的ASCII碼.
        cout<<" ";
        InOrderTraverse(T->LChild);
        InOrderTraverse(T->RChild);
    }
    else
    {
        ;
    }
}
           

        在此，我感覺很有必要和大家說明為什麼可以用遞歸算法來實作二叉樹的先序周遊操作：對于每一個結點來說，先序周遊操作的流程都是"周遊該結點---->先序周遊該結點的左子樹---->先序周遊該結點的右子樹". 我們可以發現，這種操作流程對于每一個結點來說都是相同的，是以我們可以設計出解決該問題的遞歸算法. 

        遞歸算法的設計除了要給出每次流程相同的操作外，還要給出一個明确的遞歸出口，否則程式将無窮無盡的執行下去.

        二叉樹的先序周遊算法的明确出口應該為"當結點為空"，也即"T!=NULL". 綜合上述分析，便得出二叉樹先序周遊的遞歸算法.

        我們趁熱打鐵，趁機再掌握二叉樹中序周遊遞歸算法和二叉樹後序周遊遞歸算法.

        下面給出二叉樹中序周遊的遞歸算法.

void InOrderTraverse(BiTreeNode* &T)//中序周遊通路二叉樹
{
    if(T!=NULL)
    {
        InOrderTraverse(T->LChild);
        putchar(T->data);//在螢幕上顯示字元, 若直接用cout<<T->data, 則輸出的字元的ASCII碼.
        cout<<" ";
        InOrderTraverse(T->RChild);
    }
    else
    {
        ;
    }
}
           

        再給出二叉樹後序周遊的遞歸算法. 

void InOrderTraverse(BiTreeNode* &T)//後序周遊通路二叉樹
{
    if(T!=NULL)
    {
        InOrderTraverse(T->LChild);
        InOrderTraverse(T->RChild);
        putchar(T->data);//在螢幕上顯示字元, 若直接用cout<<T->data, 則輸出的字元的ASCII碼.
        cout<<" ";
    }
    else
    {
        ;
    }
}
           

        對比看二叉樹的三種遞歸周遊算法，它們在形式上非常類似，讀者隻需記住每種周遊算法對應的結構即可，個人認為不必深究遞歸算法的執行流程. 不過喜歡刨根問底的朋友一定很想弄清執行流程, 其實也不難, 在日後的部落格中我會和大家分享這一部分的具體分析過程. 如果僅是為了準備考試，可以選擇性忽略這一部分的具體分析過程；但如果是為了提升能力, 那麼最好花時間将此過程吃透, 以為更進階别的算法設計打下堅實的基礎.

        上面的算法是二叉樹一切操作的基礎，讀者應牢牢掌握. 下面我們再來分享一個關于二叉樹的算法——求二叉樹深度的遞歸算法. 

        先給出算法的執行流程.

int Depth(BiTreeNode* &T)//計算二叉樹的深度
{
    int m,n;
    if(T!=NULL)//如果T不是空樹
    {
        m=Depth(T->LChild);//遞歸計算左子樹的深度
        n=Depth(T->RChild);//遞歸計算右子樹的深度
        if(m>n)//如果左子樹深度>右子樹深度
        {
            return m+1;//那麼傳回左子樹深度+1
        }
        else//如果右子樹深度>左子樹深度
        {
            return n+1;//那麼傳回右子樹深度+1
        }
    }
    else//如果T是空樹
    {
        return 0;//那麼傳回0
    }
}
           

        由于在二叉樹深度的計算過程中，對于每一個結點來說都要執行"求該結點的左子樹深度---->求該結點的右子樹深度---->比較該結點左子樹和右子樹的深度---->将‘深度較大者+1’作為該結點構成的二叉樹的深度"，故依舊可以使用遞歸思想解決該問題.

        我個人認為用遞歸思想解決某一複雜問題時，重要的不是用代碼實作出來并運作驗證，而是分析該問題的思維流程.

        使用遞歸算法求解問題對算法設計者而言是十分友好的，但凡事總有利弊. 算法設計者的确舒服了，但計算機可就沒那麼輕松了. 看似短短幾行的遞歸算法簡潔明了，可真正執行時，要耗費大量的主存空間，即空間效率極低. 從這裡我們也可以得出一個結論，做什麼事情時都不要劍走偏鋒，一定要多方面考慮，最終選擇最優者. 

        為了給讀者進一步加深這種思想的滲透，在高等數學一進制函數極限問題求解時的思維過程也是一個活生生的例子. 在求解一進制函數極限問題時，我們可以使用"等價無窮小替換"、"洛必達法則"和"泰勒公式展開"三種工具進行求解：可如果你隻使用"等價無窮小替換"作為求解工具，那麼很多難題你都無法解決；如果你隻使用"洛必達法則"，那麼你很有可能會掉入出題人的陷阱中；如果你隻使用高大上的"泰勒公式"，那麼你可能會将簡單的問題複雜化，進而浪費大量的解題時間. 

        是以，大家在學習時，一定要多方位思考，而不要僅停留在某種思想上. 如果你平時掌握了兩種甚至三種求解思路，那麼在考場上，你就可以随心所欲地按照自己的喜好來選擇，而不是明知某種方法求解很困難卻又隻能這麼做.

        好的，本篇博文就和大家分享至此，感謝大家的閱讀！