生成給出的順序和前序遍歷

Question

我看到代碼在這裏貼出後序遍歷： How do I output the preorder traversal of a tree given the inorder and postorder tranversal?

我不太懂其中的邏輯雖然，特別是遞歸的右部的樹：

postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1); 

任何幫助，將不勝感激。

Answer 1

承擔binary expression tree以及如何序，序和後序遍歷行事就可以了：

1. inorder：左子樹，當前根，右子樹
2. preorder：當前根，左子樹，右子樹
3. postorder：左子樹，右子樹，當前根

現在的當前代碼，第一鑑定者通知左右子樹。因爲我們知道前序數組的第一個元素是我們的根，我們可以在inorder數組中找到相應的根。因爲我們知道root之前的所有元素都是子樹的元素，並且它之後的所有元素都是正確的子樹的元素。

我們要生產後序遍歷，所以我們遞歸地用左子樹繼續：

postorder(preorder, prestart+1, inorder, inostart, i-inostart); 

1. 預啓動+ 1：因爲左子樹的根就在序遍歷當前根後
2. i-inostart：因爲i是我們在根中的索引ar射線所以I-inostart將左子樹的大小

然後右子樹：

postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1); 

1. 預起動+ I-inostart + 1：如我告訴上述i-inostart是左子樹的大小，我們也知道在前序數組中，右子樹的根將在當前根和整個子樹之後，所以它的索引將是預起動+ I-inostart + 1
2. I + 1：因爲在序陣列根指數爲我，之後的元素應該是右子樹的序陣列開始
3. 長度-I + inostart-1：因爲右子樹的大小將是長度減去左子樹的大小和減1（根）

，然後輸出我們的當前根：

cout<<preorder[prestart]<<" "; 

這樣遞歸會導致樹的後序遍歷。