前/中/后綴表達(dá)式的轉(zhuǎn)換
?
?
??? 自然表達(dá)式轉(zhuǎn)換為前/中/后綴表達(dá)式，其實(shí)是很簡單的。首先將自然表達(dá)式按照優(yōu)先級順序，構(gòu)造出與表達(dá)式相對應(yīng)的二叉樹，然后對二叉樹進(jìn)行前/中/后綴遍歷，即得到前/中/后綴表達(dá)式。
?
??? 舉例說明將自然表達(dá)式轉(zhuǎn)換成二叉樹：
?
??? a×(b+c)-d
?
??? ① 根據(jù)表達(dá)式的優(yōu)先級順序，首先計(jì)算(b+c)，形成二叉樹
??? 
???
??? ②然后是a×(b+c)，在寫時(shí)注意左右的位置關(guān)系
??? 
?
??? ③最后在右邊加上 -d
??? 
?
?
??? 然后最這個(gè)構(gòu)造好的二叉樹進(jìn)行遍歷，三種遍歷的順序分別是這樣的：
?
??? ① 前序遍歷：根-左-右
??? ② 中序遍歷：左-根-右
??? ③ 后序遍歷：左-右-根
?
??? 所以還是以剛才的這個(gè)例子，在最終二叉樹的基礎(chǔ)上可以得出：
?
??? 前綴表達(dá)式：-*a+bcd
??? 中綴表達(dá)式：a*b+c-d
??? 后綴表達(dá)式：abc+*d-
?
?
?
??? 一些其他的遍歷原則：
?
??? 1、深度優(yōu)先遍歷：
?
??? 首先訪問出發(fā)點(diǎn)V，并將其標(biāo)記為已訪問過；然后依次從V出發(fā)搜索V的每個(gè)鄰接點(diǎn)W。若W未曾訪問過，則以W為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)V有路徑相通的頂點(diǎn)(亦稱為從源點(diǎn)可達(dá)的頂點(diǎn))均已被訪問為止。若此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均被訪問為止。
?
??? 2、廣度優(yōu)先遍歷：
?
??? 首先訪問出發(fā)頂點(diǎn)V，然后訪問與頂點(diǎn)V鄰接的全部未被訪問過的頂點(diǎn)W0,W1,...WK-1；接著再依次訪問與頂點(diǎn)W0,W1,...WK-1鄰接的全部未被訪問過的頂點(diǎn)，以此類推，直至圖的所有頂點(diǎn)都被訪問到，或出發(fā)頂點(diǎn)V所在的連通分量的全部頂點(diǎn)都被訪問到為止。
?
??? 注：對于樹來說，深度優(yōu)先就是從左到右,從上到下；廣度優(yōu)先就是從上到下,從左到右。
?
-The End-