# 前序 後序 中序 遍歷 依據跟節點所在位置分為3種 1. 前序遍歷 : 根節點、左子節點、右子節點 2. 中序遍歷 : 左子節點、根節點、右子節點 2. 後序遍歷 : 左子節點、右子節點、根節點 ## 轉換 一、後序+中序 ```cpp= 假設: 後續:gdbehfca 中序:dgbaechf ``` 1. 根據後序序列的最後一個建立根節點 ```cpp= 後續:gdbehfc a root=a; ``` 2. 在中序中,利用根節點切割左子樹和右子樹 ```cpp= 中序:dgb a echf left:dgb right:echf ``` 3. 在後序中,確認左子樹和右子樹的後序序列 ```cpp= 後續:gdb ehfc a ``` 4. 重複第一步驟依序還原左子樹和右子樹 二、前序+中序 ```cpp= 假設: 前續:abdgcefh 中序:dgbaechf ``` 1. 根據前序序列的第一個建立根節點 ```cpp= 前續:a bdgcefh root=a; ``` 2. 在中序中,利用根節點切割左子樹和右子樹 ```cpp= 中序:dgb a echf left:dgb right:echf ``` 3. 在前序中,確認左子樹和右子樹的前序序列 ```cpp= 前續:a bdg cefh ``` 4. 重複第一步驟依序還原左子樹和右子樹 三、前序加後序 只能斷定父子關係,無法還原成原來的樹 ## 實作 給前序遍歷和中序遍歷,求後續遍歷 ``` preorder: GDAFEMHZ inorder: ADEFGHMZ postorder: AEFDHZMG ``` 因為前序遍歷會先走根結點,所以G為整棵樹的根結點,再根據中序遍歷,求出G的左邊為左子樹,G的右邊為右子樹,依序遞迴左右子樹,因為後續遍歷最後才紀錄根結點,所以要先遞迴完左右子樹才能輸出 ```cpp= string preorder,inorder; void rec(int pre_idx,int l,int r){ //pre_idx為當前根結點,並且在inorder的[l,r]區間遞迴 charoot=preorder[pre_idx]; //紀錄當前根結點 if(l<r){ //不是葉節點才進去 int mid=l; while(inorder[mid]!=root){ //找到根結點的位置 mid++; } if(mid>l) rec(pre_idx+1,l,mid-1); //如果左邊還有子樹才要遞迴 if(mid<r) rec(pre_idx+1+(mid-l),mid+1,r); //如果右邊還有子樹才要遞迴 } cout << root; } ```