天天看點

二叉樹求解前序序列、中序序列、後序序列

前序序列:根左右;

中序序列:左根右;

後序序列:左右根。

從以下例子可以非常清楚地明白

圖源參考

對于前序和中序的情況

前序序列:根左右

中序序列:左根右

1. 先找出前序的第一個節點(根節點),然後從中序,根據根節點分為左邊樹與右邊樹,然後再根據前序中緊鄰根節點的元素,确定好根節點緊鄰的第一個元素;

2. 然後就是套娃的過程:将緊鄰根節點的元素作為

“根節點”

,從中序,根據

“根節點”

分出其左邊樹與右邊樹,再根據前序中緊鄰

“根節點”

的元素繼續找出下一個,直到結束。。。

二叉樹求解前序序列、中序序列、後序序列

對于中序和後序的情況

中序序列:左根右

後序序列:左右根

例子如下:

一棵二叉樹的後序周遊序列為DGJHEBIFCA ,中序周遊序列為DBGEHJACIF,還原二叉樹。

與前中序同樣的道理,隻是根節點在後序中的最後。

根據後序結果,根節點為A,從中序将節點分為左邊樹與右邊樹,然後找緊鄰A的元素,即C為CIF一邊的

根節點

然後又開始套娃,除去AC後,說明F也是IF的

根節點

,這樣,一邊的就結束了,然後繼續套娃。。。

需要注意的是,别忘了左右樹的方向差別

結果如下:

二叉樹求解前序序列、中序序列、後序序列

繼續閱讀