1. 遍歷簡(jiǎn)介：

樹(shù)作為非線性數(shù)據(jù)結(jié)構(gòu)，在我們?nèi)〕鰯?shù)據(jù)時(shí)就需要設(shè)計(jì)遍歷，所謂遍歷，就是按照一定的規(guī)則性，將數(shù)據(jù)結(jié)構(gòu)中的所有數(shù)據(jù)全部依次訪問(wèn)，而二叉樹(shù)本身并不具有天然的全局次序，故為實(shí)現(xiàn)遍歷，需通過(guò)在各節(jié)點(diǎn)與其孩子之間約定某種局部次序，間接地定義某種全局次序，這便是我們常規(guī)定的先序，中序，后續(xù)遍歷。

在開(kāi)始前，請(qǐng)記住下面的這三句話：

先序遍歷：根左右

中序遍歷：左根右

后序遍歷：左右根

2. 先序遍歷：

先序遍歷就是在訪問(wèn)二叉樹(shù)的結(jié)點(diǎn)的時(shí)候采用，先根，再左，再右的方式，對(duì)于一個(gè)最簡(jiǎn)單的訪問(wèn)而言如圖，先序遍歷的訪問(wèn)順序就是A，B，C

然而實(shí)際上的遍歷訪問(wèn)并沒(méi)有那么簡(jiǎn)單，往往是多個(gè)結(jié)點(diǎn)相互嵌套構(gòu)成的二叉樹(shù)，

如圖所示，在訪問(wèn)遍歷一開(kāi)始的時(shí)候，先訪問(wèn)根結(jié)點(diǎn)A，次訪問(wèn)左節(jié)點(diǎn)B，由于左結(jié)點(diǎn)中嵌套了一組結(jié)點(diǎn)，因此左節(jié)點(diǎn)又作為下一個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)，因此就繼續(xù)沿著B(niǎo)訪問(wèn)到了D，同樣由于D中包含了一組新的結(jié)點(diǎn)，D又作為根節(jié)點(diǎn)繼續(xù)訪問(wèn)，就又訪問(wèn)到了E，由于E沒(méi)有后面的結(jié)點(diǎn)了，作為D為根的左結(jié)點(diǎn)E訪問(wèn)結(jié)束后，訪問(wèn)到F，這一組訪問(wèn)結(jié)束之后再回退訪問(wèn)G……

由此如下的訪問(wèn)規(guī)律：這一個(gè)二叉樹(shù)的先序遍歷訪問(wèn)順序就是：ABDEFGCH

3. 代碼實(shí)現(xiàn)

續(xù)上文的代碼，實(shí)現(xiàn)先序遍歷思路非常簡(jiǎn)單，只需要巧妙的利用“遞歸”即可。

//樹(shù)的先序遍歷 Preorder traversal
void preorder(Node* node){
    if (node != NULL)
    {
        printf("%d ",node->data);
        inorder(node->left);
        inorder(node->right);
    }
}

4. 擴(kuò)展：前綴表達(dá)式（波蘭式）

波蘭式又稱為前綴表達(dá)式，我們?nèi)粘５倪\(yùn)算表達(dá)式通常是如下形式，這種成為中綴表達(dá)式，也就是運(yùn)算符在運(yùn)算數(shù)的中間。這種表達(dá)式人類(lèi)人容易識(shí)別，并根據(jù)其進(jìn)行計(jì)算，但計(jì)算機(jī)識(shí)別這種表達(dá)式非常困難。

如圖，為常規(guī)表達(dá)式：(a+b)*c

其二叉樹(shù)的表現(xiàn)形式為：

而波蘭式的表達(dá)方式就是 *+cab ，波蘭式的一個(gè)特征就是符號(hào)遷移，常規(guī)的表達(dá)式是需要大量的括號(hào)表達(dá)先后順序的，而這樣的波蘭式表達(dá)形式不需要，更容易讓計(jì)算機(jī)處理，我們常規(guī)的表達(dá)式的計(jì)算是中序的，而計(jì)算機(jī)更方便對(duì)波蘭式這樣的方式進(jìn)行理解，進(jìn)行這樣的轉(zhuǎn)換首先思路要進(jìn)行轉(zhuǎn)換，在代碼中我們實(shí)現(xiàn)這樣的轉(zhuǎn)換一般可以利用棧，熟練書(shū)些這樣的轉(zhuǎn)換就需要STL的掌握，這點(diǎn)作為擴(kuò)展內(nèi)容自行學(xué)習(xí)。

5. 相關(guān)習(xí)題

l  二叉樹(shù)的遍歷習(xí)題：http://www.sztianhecheng.cn/oj/problem1734.html

請(qǐng)回答

l  這一顆樹(shù)的先序遍歷是多少？