二叉樹的前中后序你真的懂了嗎
首先觀察前中后序的排列方式
前中后序列的左右子樹的順序是不會改變的
唯一會改變的就是根節點的位置
ok
回到前中后
前序就是根節點在前面（根左右）
中序就是根節點在中間（左根右）
后序就是根節點在末端（左右根）
例如給一個二叉樹
觀察這個二叉樹
我們使用前序遍歷
根據我們剛才的根左右的順序來解答這個二叉樹
從左到右我們分別命上編號
A
BC
DEF
觀察第一個根節點
就是我們的首結點
根左右的順序來看這個二叉樹下面的部分我們先不看
只看上面前兩層
根據前序根左右我們可以得到ABC
但是我們的B結點在他的子數里面又是一個根節點，所以這個地方我們再把B展開
B根據根結點的排序我們可以得到一個新的就是
根左（根左右BDE）右
即為我們將B替換為BDE
現在我們的前序序列為A*BDE*C
繼續展開我們的右邊的樹
即為C展開為CF根左右沒有左結點 使用我們的C變成CF序列
現在我們的所有結點全部排序完畢
我們得到了全部的結點為
ABDECF
他們的遍歷代碼類似
我們可以簡潔的清晰記憶
此處我們用C語言描述一下
稍等補上
用遞回遍歷
void PreOrder(BiTree T)
{
if(T!=Null)
{
visit(T); //訪問根節點，這一行的位置不一樣就是對應的遍歷 不一樣，看下一行PreOrder訪問的是lchild也就是說如果我們的左節點不為空的話，會呼叫自己這個函式來訪問左節點，函式的引數就是T ，對應著我們的理解就是把左子點當成根節點，符合了我們的遍歷思想，
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
這個樹的中序遍歷也就是左根右的順序
同理我們進行一下遍歷
可能會對這個遍歷帶入一下就得到了
DBE
沒錯你得到了左子樹得全部結點
繼續帶入（DBE）A（C）發現還少一個結點
我們把C的子樹當成一個新的子樹
空CF
是不是得到了一個右邊得結點
串聯起來就是
DBEACF
后序遍歷為
左右根
DEBFCA
看一下下一篇關于這三種遍歷的拓展到B樹，我感覺你應該對遍歷會有一個新的認識，看一看吧，，，，，，，，，，，，，那一篇能解決大部分的前中后序遍歷，
鏈接: B樹拓展.
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/3372.html
標籤：其他