前序序列:根左右;
中序序列:左根右;
後序序列:左右根。
從以下例子可以非常清楚地明白
圖源參考
對于前序和中序的情況
前序序列:根左右
中序序列:左根右
1. 先找出前序的第一個節點(根節點),然後從中序,根據根節點分為左邊樹與右邊樹,然後再根據前序中緊鄰根節點的元素,确定好根節點緊鄰的第一個元素;
2. 然後就是套娃的過程:将緊鄰根節點的元素作為
“根節點”
,從中序,根據
“根節點”
分出其左邊樹與右邊樹,再根據前序中緊鄰
“根節點”
的元素繼續找出下一個,直到結束。。。
對于中序和後序的情況
中序序列:左根右
後序序列:左右根
例子如下:
一棵二叉樹的後序周遊序列為DGJHEBIFCA ,中序周遊序列為DBGEHJACIF,還原二叉樹。
與前中序同樣的道理,隻是根節點在後序中的最後。
根據後序結果,根節點為A,從中序将節點分為左邊樹與右邊樹,然後找緊鄰A的元素,即C為CIF一邊的
根節點
;
然後又開始套娃,除去AC後,說明F也是IF的
根節點
,這樣,一邊的就結束了,然後繼續套娃。。。
需要注意的是,别忘了左右樹的方向差別
結果如下: