有根樹相關知識總結之周遊二叉樹（C語言描述）

前言：二叉樹的周遊方法主要有前序周遊、中序周遊、後續周遊和層序周遊。各算法又可分為遞歸算法和非遞歸算法兩種，本文将進行區分讨論。從本質上來說，二叉樹的深度優先搜尋包括了前序周遊、中序周遊和後續周遊；廣度優先搜尋即是層序周遊。

1. 二叉樹的資料結構定義（C語言版）

typedef struct BiNode
{
    char m_data;//資料域
    struct BiNode *plChild;//左孩子節點
    struct BiNode *prChild;//右孩子節點
}BiNode,*BiTree;

2.二叉樹的前序周遊（遞歸版本）

算法思想：

因為周遊過程對每個節點都會通路一次，包括那些為空的節點。遞歸算法主要需要考慮遞歸出口的問題，如果二叉樹節點為NULL（如最左下節點的左孩子即為空），則return即可；

源碼描述：

void PreOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //遞歸出口，節點為NULL，則傳回
        return; 
    else
    {
        printf("%c",pRoot->m_data);//周遊根節點
        PreOrderWalkTree(pRoot->plChild);//周遊左子樹
        PreOrderWalkTree(pRoot->prChild);//周遊右子樹
    }
    printf("\n");
}

3.二叉樹的前序周遊（非遞歸版本）、

算法思想：

前序周遊即對每個節點首先将通路根節點，然後通路左子樹，最後通路右子樹。由于對于每個節點都遵循這樣的順序，最後通路右子樹，是以必須先将根節點儲存，即入棧；由于最先通路根節點，是以在入棧的時候就可以通路它。通路完左子樹，即可出棧并擷取其右子樹，進而對右子樹進行通路。

源碼描述：

void PreOrderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//建立節點類型的棧

    BiNode *pCurNode=pRoot;//目前節點
    //1. 進入主循環
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            Visit(pCurNode);//通路目前節點
            PushElement(&NodeStack,pCurNode);//将目前節點入棧
            pCurNode=pCurNode->plChild;//沿着一條路走到最左下節點,即碰到左孩子為空
        }

        if (!IsStackEmpty(&NodeStack))
        {
            pCurNode=PopElement(&NodeStack);//碰到左孩子為空就要出棧，此時棧頂元素是目前節點
            pCurNode=pCurNode->prChild;
        }
    }
}

4.二叉樹的中序周遊（遞歸版本）

算法思想：

源碼描述：

void InOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //遞歸出口，節點為NULL，則傳回
        return; 
    else
    {
        PreOrderWalkTree(pRoot->plChild);//周遊左子樹
        printf("%c",pRoot->m_data);//周遊根節點
        PreOrderWalkTree(pRoot->prChild);//周遊右子樹
    }
    printf("\n");
}

5.二叉樹的中序周遊（非遞歸版本）

算法思想

中序周遊是先通路節點的左子樹，然後通路根節點，再通路右子樹。和前序周遊類似，由于右子樹是最後通路，是以必須要儲存根節點以在左子樹和根節點都通路完了之後擷取右子樹進而對其通路。具體的說，需要将根節點沿着左子樹路徑入棧，碰到左孩子為空–>出棧–>通路根節點–>擷取右孩子。

源碼描述：

void InOderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//建立節點類型的棧

    BiNode *pCurNode=pRoot;
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            PushElement(&NodeStack,pCurNode);//目前節點入棧
            pCurNode=pCurNode->plChild;
        }//直到碰到左孩子為空為止

        if (!IsStackEmpty(&NodeStack))
        {
            pCurNode=PopElement(&NodeStack);
            Visit(pCurNode);//出棧的時候通路節點
            pCurNode=pCurNode->prChild;//處理右孩子
        }
    }
}

6.二叉樹的後序周遊（遞歸版本）

算法思想：

源碼描述：

void PostOrderWalkTree(BiNode *pRoot)
{
    if (pRoot==NULL) //遞歸出口，節點為NULL，則傳回
        return; 
    else
    {
        PreOrderWalkTree(pRoot->plChild);//周遊左子樹
        PreOrderWalkTree(pRoot->prChild);//周遊右子樹
        printf("%c",pRoot->m_data);//周遊根節點
    }
    printf("\n");
}

7.二叉樹的後序周遊（非遞歸版本）

算法思想

前序周遊和中序都是最後通路右子樹是以需要借助棧儲存根節點，後序周遊是先通路左子樹，其次通路右子樹，最後通路根節點。由于是先左子樹後右子樹，是以仍然需要儲存根節點以擷取右子樹。另一方面，當左子樹為空時，此時根節點位于棧頂，需要判斷右子樹是否已經被通路過，如果右子樹沒有被通路，則根節點不出棧，繼續通路右子樹；如果右子樹已經被通路，則根節點出棧，通路根節點。是以，根節點有兩次位于棧頂，第二次時才出棧。

源碼描述：

void PostOderWalkTree(BiNode *pRoot)
{
    BiNodeStack NodeStack;
    InitStack(&NodeStack);//建立節點類型的棧
    int i=;
    bool brChlidNotProced[MaxStackSize];

    BiNode *pCurNode=pRoot;
    while (pCurNode!=NULL||!IsStackEmpty(&NodeStack))
    {
        while (pCurNode)
        {
            PushElement(&NodeStack,pCurNode);//目前節點入棧
            brChlidNotProced[i++]=false;//表示右孩子還沒有處理
            pCurNode=pCurNode->plChild;
        }//直到碰到左孩子為空為止

        if (!brChlidNotProced[i-]) //右孩子沒有被處理
        {
            pCurNode=GetStackTop(&NodeStack);//擷取棧頂元素，未出棧
            pCurNode=pCurNode->prChild;
            brChlidNotProced[i-]=true;
        }
        else
        {
            pCurNode=PopElement(&NodeStack);//右子樹已經處理，可以出棧
            Visit(pCurNode);//通路
            i--;
            pCurNode=NULL;//棧頂元素彈出并通路後，還要進行一次出棧操作
        }
    }
}

8.二叉樹的層序周遊（非遞歸版本）

算法思想：

由于對于每一層都需要從左向右周遊節點，是以有“先入先出”的意思，采用隊列進行描述。首先将根節點入隊列，其次進入主循環，目前節點出隊列并通路，如果其左孩子不為空，則左孩子入隊列，如果右孩子不為空，則右孩子入隊列。

源碼描述：

void LayerOderWalkTree(BiNode *pRoot)
{
    BiNodeQueue NodeQueue;
    InitQueue(&NodeQueue);//初始化隊列

    BiNode *pCurNode=pRoot;
    EnQueue(&NodeQueue,pCurNode);//根節點入隊列

    //進入主循環，直至隊列為空
    while (!IsQueueEmpty(&NodeQueue))
    {
        pCurNode=DeQueue(&NodeQueue);
        Visit(pCurNode);//通路目前節點

        if (pCurNode->plChild!=NULL) //左孩子不為空，則進隊列
        {
            EnQueue(&NodeQueue,pCurNode->plChild);
        }

        if (pCurNode->prChild!=NULL) //右孩子不為空，則進隊列
        {
            EnQueue(&NodeQueue,pCurNode->prChild);
        }
    }
}

總結：以上四種周遊算法的實作均采用教科書上的思想，即：

前序周遊：目前節點是在入棧的時候被通路；
中序周遊：目前節點是在出棧的時候被通路；
後續周遊：目前節點是在第二次在棧頂的時候被通路；有兩次出現的棧頂，第一次是右子樹未處理的時候，第二次是右子樹處理完了的時候。是以需要标記位bFlag用于辨別右子樹是否被處理：

3.1 bFlag=1,右子樹未處理->不出棧，處理右子樹;

3.2 bFlag=0,右子樹已處理->出棧，通路目前節點;
層序周遊：目前節點出隊列的時候被通路；同時将其不為空的孩子節點入隊列。

樹的深度優先搜尋和廣度優先搜尋：

樹的深度優先搜尋是指首先從樹的根節點出發，然後選擇一個與其相鄰的且未被通路的頂點（孩子節點），依次進行，直到某個節點與其相鄰的所有節點都已經被通路或者為空為止。然後退回到已經被通路的頂點序列中最後一個擁有未被通路的鄰接節點的節點。直至所有節點均已經被通路。
樹的廣度優先搜尋是指首先從樹的根節點出發，周遊與其相鄰的所有節點，然後再周遊這些鄰接節點的鄰接節點，依次進行下去，直至所有節點均已經被通路。

有根樹相關知識總結之周遊二叉樹（C語言描述）

繼續閱讀

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

[轉]ISUP信令的IAM消息詳細内容

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希