一.二叉樹(shù)的遍歷：

按照一定規(guī)律對(duì)二叉樹(shù)的每個(gè)結(jié)點(diǎn)進(jìn)行訪問(wèn)且僅訪問(wèn)一次；

這里的訪問(wèn)：可以是計(jì)算二叉樹(shù)中的結(jié)點(diǎn)數(shù)據(jù)，打印該結(jié)點(diǎn)的信息，也可以是對(duì)結(jié)點(diǎn)進(jìn)行的任何其它操作！

為什么需要遍歷二叉樹(shù)？

從過(guò)遍歷可以得到訪問(wèn)結(jié)點(diǎn)的順序序列，遍歷操作就是將二叉樹(shù)的結(jié)點(diǎn)按一定的規(guī)律線性化，目的就在于將非線性化的結(jié)構(gòu)變成線性化的訪問(wèn)序列。

二.3種遍歷方式：

1.先序遍歷：（DLR）根——左——右

若二叉樹(shù)非空：

首先訪問(wèn)根結(jié)點(diǎn)，其次按先序遍歷左子樹(shù)，最后按先序遍歷右子樹(shù)

下面我們給出一個(gè)例子：

如圖所示的二叉樹(shù)：根據(jù)先序遍歷的特點(diǎn)，我們先訪問(wèn)根結(jié)點(diǎn)：A，再訪問(wèn)其左子樹(shù),而其左子樹(shù)又可以看成一個(gè)二叉樹(shù)，我們依然用先序遍歷A的左子樹(shù)，此時(shí)B為這個(gè)左子樹(shù)的根結(jié)點(diǎn)，于是我們?cè)L問(wèn)B，A的左子樹(shù)此時(shí)還沒(méi)有訪問(wèn)完成，因此我們繼續(xù)訪問(wèn)，此時(shí)B已經(jīng)訪問(wèn)過(guò)，那么我們接著訪問(wèn)B的左孩子，而B(niǎo)沒(méi)有左孩子，所以我們接著訪問(wèn)B的右孩子，D作為右孩子的根結(jié)點(diǎn)，直接訪問(wèn)，對(duì)于D來(lái)說(shuō)，接著訪問(wèn)D的左孩子F，最后訪問(wèn)D的右孩子G；此時(shí)A的左孩子遍歷完成；

那么我們接著遍歷A的右孩子，C作為右子樹(shù)的根結(jié)點(diǎn)直接訪問(wèn)，C沒(méi)有左孩子，接著訪問(wèn)C的右孩子，E作為C的右孩子的根節(jié)點(diǎn)，直接訪問(wèn)，E沒(méi)有左孩子，訪問(wèn)E的右孩子H；

綜上所述：上述二叉樹(shù)的先序遍歷的順序就為：A-B-D-F-G-C-E-H

2.中序遍歷：LDR（左——根——右）

我們?nèi)匀灰陨鲜龆鏄?shù)為例來(lái)看：

根據(jù)?中序遍歷的特點(diǎn)：首先按中序遍歷左子樹(shù)：此時(shí)首先訪問(wèn)A的左子樹(shù)，我們將二叉樹(shù)的左子樹(shù)單獨(dú)拿出來(lái)看：如圖：B作為左子樹(shù)的根節(jié)點(diǎn)，我們要找此時(shí)這個(gè)二叉樹(shù)的左孩子，而此時(shí)這個(gè)二叉樹(shù)沒(méi)有左孩子，因此我們直接訪問(wèn)這個(gè)二叉樹(shù)的根節(jié)點(diǎn)B，之后訪問(wèn)這個(gè)二叉樹(shù)的右孩子：同樣把這個(gè)二叉樹(shù)的右孩子單獨(dú)拿出來(lái)：此時(shí)我們依然以中序遍歷：首先訪問(wèn)這個(gè)二叉樹(shù)的左孩子，即F，接著訪問(wèn)這個(gè)二叉樹(shù)的根節(jié)點(diǎn)D,最后訪問(wèn)這個(gè)二叉樹(shù)的右孩子G；

那么此時(shí)整個(gè)二叉樹(shù)的左孩子訪問(wèn)完成，繼續(xù)訪問(wèn)整個(gè)二叉樹(shù)的根節(jié)點(diǎn)A；

接著訪問(wèn)整個(gè)二叉樹(shù)的右孩子：

此時(shí)C作為整個(gè)二叉樹(shù)的右孩子的根節(jié)點(diǎn)，我們首先訪問(wèn)這個(gè)二叉樹(shù)的左孩子，顯然這個(gè)二叉樹(shù)沒(méi)有左孩子，因此我們先訪問(wèn)根結(jié)點(diǎn)C；

此時(shí)：E作為二叉樹(shù)的根結(jié)點(diǎn)，此時(shí)該二叉樹(shù)沒(méi)有左孩子，直接訪問(wèn)根節(jié)點(diǎn)E，最后訪問(wèn)右孩子H

綜上所述：按照中序遍歷訪問(wèn)上述二叉樹(shù)的順序：B-F-D-G-A-C-E-H

3.后序遍歷：LRD（左——右——根）

仍然以上述二叉樹(shù)作為例子來(lái)看：首先訪問(wèn)整個(gè)二叉樹(shù)的左子樹(shù)：

按照后序遍歷訪問(wèn)：B作為根結(jié)點(diǎn)，訪問(wèn)這個(gè)二叉樹(shù)的左子樹(shù)，左子樹(shù)為空，接著訪問(wèn)這個(gè)二叉樹(shù)的右孩子：

此時(shí)D作為根結(jié)點(diǎn)，先訪問(wèn)其左孩子F，接著訪問(wèn)其右孩子G，最后訪問(wèn)根節(jié)點(diǎn)D；

那么經(jīng)過(guò)上述過(guò)程，該二叉樹(shù)的右孩子訪問(wèn)完成，接著訪問(wèn)根節(jié)點(diǎn)B，此時(shí)整個(gè)二叉樹(shù)的左子樹(shù)遍歷完成；

那么我們接著訪問(wèn)整個(gè)二叉樹(shù)的右子樹(shù)：

C作為此時(shí)這個(gè)二叉樹(shù)的根結(jié)點(diǎn)，先訪問(wèn)這個(gè)二叉樹(shù)的左子樹(shù)，但是左子樹(shù)為空，接著訪問(wèn)右孩子：

E為此時(shí)這個(gè)二叉樹(shù)的根結(jié)點(diǎn)，此時(shí)這個(gè)二叉樹(shù)沒(méi)有左子樹(shù)，那么我們?cè)L問(wèn)其右孩子H，接著訪問(wèn)根節(jié)點(diǎn)E；

此時(shí)這個(gè)二叉樹(shù)的右孩子也訪問(wèn)完成，所以我們?cè)L問(wèn)根結(jié)點(diǎn)C；

整個(gè)二叉樹(shù)的左右子樹(shù)均已遍歷完成，于是我們最后訪問(wèn)根結(jié)點(diǎn)A；

綜上所述：按照后續(xù)遍歷訪問(wèn)上述二叉樹(shù)的順序?yàn)椋篎-G-D-B-H-E-C-A

總結(jié)：

看了以上三種方式遍歷二叉樹(shù)的例子，應(yīng)該就能明白三種遍歷方式的本質(zhì)與區(qū)別，其實(shí)我們可以看出，無(wú)論以何種方式，我們只要把握好訪問(wèn)的順序，并且將每一個(gè)根結(jié)點(diǎn)下的子樹(shù)都看成一個(gè)新樹(shù)，再按照某種遍歷方式訪問(wèn)這個(gè)這個(gè)新樹(shù)即可！

例子：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式；（前綴表達(dá)式：波蘭表達(dá)式；后綴表達(dá)式：逆波蘭表達(dá)式）

前綴表達(dá)式：-+a*bc/de（也就是以先序遍歷訪問(wèn)上述二叉樹(shù)的順序）

中綴表達(dá)式：a+b*c-d/e（也就是以中序遍歷訪問(wèn)上述二叉樹(shù)的順序）

后綴表達(dá)式：abc*+de/-（也就是以后序遍歷訪問(wèn)上述二叉樹(shù)的順序）

我們其實(shí)可以看出：中綴表達(dá)式是我們?cè)跀?shù)學(xué)計(jì)算中的習(xí)慣順序，但是其實(shí)在計(jì)算機(jī)種，后綴表達(dá)式才是計(jì)算機(jī)能理解的表達(dá)式；

（關(guān)于中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的例題：

有興趣的讀者可以自行嘗試：下面給出利用棧來(lái)解決逆波蘭表達(dá)式的代碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 1010

typedef struct
{
    char* ch;
    int top;

}CharStack;

typedef struct
{
    double* num;
    int top;
}NumStack;

CharStack S;
NumStack St;

void InitCharStack(CharStack& S);
void InitNumStack(NumStack& St);
void PushCharStack(CharStack& S, char c);
void PushNumStack(NumStack& St, double num);
char PopCharStack(CharStack& S);
double PopNumStack(NumStack& St);
char GetStackTop(CharStack& S);
bool PriorJudge(char c1, char c2);//priority優(yōu)先級(jí) judge判斷
char* InfixToSuffex(char* a, char* b);//infix前綴 suffex后綴 
double CaculatValue(char* b, NumStack& St);

int main()
{
    InitCharStack(S);

    char a[MaxSize] = { 0 };
    char b[MaxSize] = { 0 };
    InfixToSuffex(a, b);

    double ans = CaculatValue(b, St);

    printf("%.2f\n", ans);

    return 0;
}

void InitCharStack(CharStack& S)
{
    S.ch = (char*)malloc(MaxSize * sizeof(char));

    if (S.ch == NULL)
    {
        printf("內(nèi)存分配失??！");
        return;
    }
    S.top = -1;

    return;
}

void PushCharStack(CharStack& S, char c)
{
    if (S.top == MaxSize)
    {
        printf("棧已滿(mǎn)");
        return;
    }
    S.top++;
    *++S.ch = c;

    return;
}

char PopCharStack(CharStack& S)
{
    if (S.top == -1)
    {
        printf("棧為空");;
        exit(1);
    }
    S.top--;
    char c = *S.ch--;

    return c;
}

char GetStackTop(CharStack& S)
{
    char c = *S.ch;

    return c;
}

bool PriorJudge(char c1, char c2)//priority優(yōu)先級(jí) judge判斷 
{
    if (c1 == '*' || c1 == '/')
        if (c2 == '+' || c2 == '-' || c2 == '(')
            return true;
    if (c1 == '+' || c1 == '-')
        if (c2 == '(') return true;

    return false;
}

char* InfixToSuffex(char* a, char* b)//infix中綴 suffex后綴 
{
    fgets(a, MaxSize - 1, stdin);//從輸入流中讀取字符串 

    int t = strlen(a);

    int k = 0;
    //    12.25 + 25.02 / 2.36 + 8 * 2.01 =
    for (int i = 0; i < t; ++i)
    {
        if (a[i] >= '0' && a[i] <= '9')
        {
            b[k++] = a[i];
            if (a[i + 1] == '.') b[k++] = '.', ++i;
            else if (a[i + 1] < '0' || a[i + 1] > '9')
                b[k++] = '#';
        }

        else if (a[i] == ' ' || a[i] == '=') continue;

        else
        {
            if (S.top == -1 || a[i] == '(')
                PushCharStack(S, a[i]);

            else if (a[i] == ')')
            {
                while (S.top != -1 && GetStackTop(S) != '(')
                    b[k++] = PopCharStack(S);

                if (S.top != -1) PopCharStack(S);

            }

            else
            {
                while (S.top != -1 && !PriorJudge(a[i], GetStackTop(S)))
                    b[k++] = PopCharStack(S);

                PushCharStack(S, a[i]);
            }
        }

    }

    b[k] = '\0';//這句話加不加應(yīng)該無(wú)所謂，因?yàn)樵撟址麛?shù)組已初始化為0 

    return b;
}

void InitNumStack(NumStack& St)
{
    St.num = (double*)malloc(MaxSize * sizeof(double));
    St.top = -1;

    return;
}

void PushNumStack(NumStack& St, double n)
{
    if (St.top == MaxSize)
    {
        printf("棧已滿(mǎn)");
        return;
    }

    St.top++;

    *++St.num = n;

    return;
}

double PopNumStack(NumStack& St)
{
    if (St.top == -1)
    {
        printf("棧為空");
        exit(1);
    }
    St.top--;
    double num = *St.num--;

    return num;
}

double CaculatValue(char* b, NumStack& St)
{
    InitNumStack(St);
    int t = strlen(b);
    char str[MaxSize] = { 0 };

    for (int i = 0, k = 0; i < t; ++i)
    {
        if (b[i] == '.' || (b[i] >= '0' && b[i] <= '9'))
        {
            str[k++] = b[i];
            if (b[i + 1] == '#')
            {
                str[k] = '\0';
                double num = atof(str);
                PushNumStack(St, num);
                k = 0;
            }
        }

        else
        {
            if (b[i] == '#') continue;

            double n = PopNumStack(St);
            double m = PopNumStack(St);

            if (b[i] == '+') PushNumStack(St, m + n);

            else if (b[i] == '-') PushNumStack(St, m - n);

            else if (b[i] == '*') PushNumStack(St, m * n);

            else PushNumStack(St, m / n);
        }

    }

    return PopNumStack(St);
}

三.二叉樹(shù)的遍歷算法：

在理解了上述所說(shuō)的遍歷過(guò)程之后，我們來(lái)看二叉樹(shù)的遍歷算法，可以分為遞歸算法與非遞歸算法

1.遞歸算法：

（1）先序遍歷的遞歸算法

首先定義二叉樹(shù)的鏈表結(jié)點(diǎn)結(jié)構(gòu)：

#define DataType int 
//首先定義二叉樹(shù)：

typedef struct Node
{
	DataType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode,*BiTree;

//先序遍歷二叉樹(shù)的遞歸算法

void PreOrder(BiTree root)
{
	//root為指向二叉樹(shù)或者其某一子樹(shù)的根結(jié)點(diǎn)的指針

	if (root != NULL)
	{
		printf("%d", root->data);//訪問(wèn)根結(jié)點(diǎn)；//文章開(kāi)頭就已經(jīng)說(shuō)過(guò)，二叉樹(shù)的遍歷可以是多種形式
		PreOrder(root->LChild);//按照先序遍歷訪問(wèn)左子樹(shù)
		PreOrder(root->RChild);//按照先序遍歷訪問(wèn)右子樹(shù)
	}
}

（2）中序遍歷遞歸算法

void InOrder(BiTree root)
{
	if (root != NULL)
	{
		InOrder(root->LChild);//首先按中序遍歷左子樹(shù)
		printf("%d", root->data);//訪問(wèn)根結(jié)點(diǎn)
		InOrder(root->RChild);//中序遍歷右子樹(shù)
	}
}

（3）后續(xù)遍歷遞歸算法

void PostOrder(BiTree root)
{
	if (root != NULL)
	{
		PostOrder(root->LChild);//首先按照后序遍歷左子樹(shù)
		PostOrder(root->RChild);//按照后序遍歷右子樹(shù)
		printf("%d", root->data);//訪問(wèn)根結(jié)點(diǎn)
	}
}

遞歸：把復(fù)雜問(wèn)題變成相同性質(zhì)的子問(wèn)題，因此遞歸算法表面上看上去很簡(jiǎn)單，其實(shí)整個(gè)的邏輯十分復(fù)雜；

比如：當(dāng)訪問(wèn)到的結(jié)點(diǎn)不為空時(shí)，我們先訪問(wèn)其左子樹(shù)，再訪問(wèn)其右子樹(shù)；但是當(dāng)根結(jié)點(diǎn)為空時(shí)，就不需要參與遞歸運(yùn)算，那此時(shí)訪問(wèn)的為空，應(yīng)該返回什么值？在這里程序就會(huì)自動(dòng)設(shè)置堆棧來(lái)保存本層地址（涉及到堆棧的知識(shí)：當(dāng)遞歸函數(shù)調(diào)用時(shí)，應(yīng)按照“后調(diào)用先返回”（因?yàn)榇髥?wèn)題一直在分解成小問(wèn)題，當(dāng)分解為基問(wèn)題時(shí)，才會(huì)返回一個(gè)值，因此最后調(diào)用的先返回）的原則處理調(diào)用過(guò)程，因此函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過(guò)棧來(lái)實(shí)現(xiàn)（符合棧的特點(diǎn)：last in first out）

整個(gè)遞歸過(guò)程其實(shí)與上述所描述的遍歷算法類(lèi)似，讀者可嘗試分析；

遞歸算法的時(shí)間復(fù)雜度分析：

假設(shè)二叉樹(shù)有n個(gè)結(jié)點(diǎn)，對(duì)每個(gè)結(jié)點(diǎn)都要進(jìn)行一次入棧和出棧的操作，即入棧和出棧均執(zhí)行了n此，對(duì)結(jié)點(diǎn)的訪問(wèn)也是n次，這些二叉樹(shù)的遞歸遍歷算法的時(shí)間復(fù)雜度就為O(n)；

A.遞歸遍歷算法的應(yīng)用：

a.輸出二叉樹(shù)中的結(jié)點(diǎn)：

//輸出二叉樹(shù)的結(jié)點(diǎn)

void PreOrder(BiTree root)
{
	if (root != NULL)
	{
		printf("%d",root->data);
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}
}

輸出二叉樹(shù)的結(jié)點(diǎn)并沒(méi)有次序要求，因此三種次序均可以使用

b.輸出二叉樹(shù)中的葉子結(jié)點(diǎn)：

相比于上述應(yīng)用，葉子節(jié)點(diǎn)：無(wú)后繼，因此有條件限制

//輸出葉子結(jié)點(diǎn)數(shù)

void PreOrder(BiTree root)
{
	if (root != NULL)
	{
		if (root->LChild == NULL && root->RChild == NULL)
		{
			printf("%d", root->data);
		}
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}
}

c.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目

（1）一般的后序遍歷

void leaf(BiTree root)
{
	if (root != NULL)
	{
		leaf(root->LChild);
		leaf(root->RChild);
		if (root->LChild == NULL && root->RChild == NULL)
		{
			leafCount++;//保存葉子結(jié)點(diǎn)數(shù)目的全局變量，調(diào)用之前的初始化為0；別忘了在main函數(shù)中先調(diào)用初始化函數(shù)
		}
	}
}

在這里：根據(jù)文章開(kāi)頭所說(shuō)的，究竟什么才是對(duì)根結(jié)點(diǎn)進(jìn)行訪問(wèn)？在這里leafCount++就可以是，因此在這里，我們使用的是后續(xù)遍歷；

（2）分治算法：

如果二叉樹(shù)為空樹(shù)，返回0，如果二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，返回1，否則返回左子樹(shù)和右子樹(shù)的葉子節(jié)點(diǎn)數(shù)之和（也是遞歸算法）

int leaf1(BiTree root)
{
	int leafCount;
	if (root == NULL)
	{
		leafCount = 0;
	}
	else if (root->LChild == NULL && root->RChild == NULL)
	{
		leafCount = 1;
	}
	else
	{
		leafCount = leaf1(root->LChild) + leaf1(root->RChild);
	}
	return leafCount;
}

在這里也是后序遍歷：根據(jù)表達(dá)式：C=A+B，在C語(yǔ)言中是先計(jì)算A，再計(jì)算B，最后計(jì)算A+B，賦值給C，因此依然是先遍歷左子樹(shù)，再遍歷右子樹(shù)，最后訪問(wèn)根；

（關(guān)于求二叉樹(shù)的高度：讀者可嘗試）

int PostTreeDepth(BiTree bt)
{
	int hl, hr,max;
	if (bt != NULL)
	{
		hl=PostTreeDepth(bt->LChild);
		hr=PostTreeDepth(bt->RChild);
		max = hl > hr ? hl : hr;
		return(max + 1);//還要加上第一個(gè)根結(jié)點(diǎn)
	}
	else
	{
		return 0;
	}
}

d:按橫向樹(shù)形顯示二叉樹(shù)：

其實(shí)就是按照“逆中序”的方式來(lái)遍歷整個(gè)二叉樹(shù)（所謂的逆中序，就是先訪問(wèn)右子樹(shù)，再訪問(wèn)根，最后訪問(wèn)右子樹(shù)，與正常的中序遍歷相反）

（在這里只給出思路，具體代碼實(shí)現(xiàn)，讀者可以自行嘗試，有問(wèn)題歡迎在評(píng)論區(qū)交流！）

2.非遞歸算法：

基于棧的遞歸消除：

關(guān)于遞歸的消除：我們可以將這些遞歸問(wèn)題，轉(zhuǎn)化為重復(fù)的循環(huán)問(wèn)題，即用循環(huán)代替遞歸，但是在工作量大，復(fù)雜的情況下，就不適宜采用循環(huán)，因此我們可以采用工作棧的方式來(lái)消除遞歸。

（1）中序遍歷二叉樹(shù)的非遞歸算法

下面我們以中序遍歷二叉樹(shù)的非遞歸算法為例來(lái)看：

整個(gè)過(guò)程都依據(jù)在上述框圖下進(jìn)行：

?（以此二叉樹(shù)為例）

首先：A：A不為空——進(jìn)棧；p=A的LChild，到B；B不為空——進(jìn)棧；p指向B的左子樹(shù)，到C；C不為空，C進(jìn)棧；p指向C的左子樹(shù)；C的左子樹(shù)為空，判斷棧是否為空，棧此時(shí)非空，C出棧，p指向C的右子樹(shù)，D，C的右子樹(shù)不為空，D入棧，p指向D的左子樹(shù)，p為空，那么判斷棧是否為空，棧非空，D退棧，p指向D的右子樹(shù)，D的右子樹(shù)為空，棧非空，退棧到B，p指向B的右子樹(shù)，為E，不是空，那么E進(jìn)棧，E的左子樹(shù)為空，棧非空，那么E出棧，p指向E的右子樹(shù)，E的右子樹(shù)為空，棧非空，A出棧，A的右子樹(shù)為F，不為空F進(jìn)棧，p指向F的左子樹(shù)，F(xiàn)的左子樹(shù)為G不為空，G進(jìn)棧，p指向G的左子樹(shù)，G的左子樹(shù)為空，棧非空，G出棧，p指向G的右子樹(shù)，G的右子樹(shù)為空，棧非空，F(xiàn)出棧，p指向F的右子樹(shù)，F(xiàn)的右子樹(shù)為空，棧為空，那么遍歷結(jié)束；（出棧的同時(shí)訪問(wèn)根結(jié)點(diǎn)，在這里我省略了，注意一下?。。?/strong>）（可能有點(diǎn)長(zhǎng)，可以耐心看一下）