用 Preorder 與 Inorder traversal 畫出 binary tree

給定一個 binary tree 的 Preorder與 Inorder traversal,證明這組 traversal,只能對應到一個獨特的 binary tree。
(前提是每一個 element 都是 unique。)

在證明之前,我們要先知道 Preorder 跟 Inorder 的特性。
Preorder 的 traversal 順序是根、左子樹、右子樹;Inorder 的 traversal 順序是左子樹、根、右子樹。

因此 Preorder 的第一個 element 會是根。
而 Preorder 的問題會是,在後面的 element,不知道有哪些是屬於左子樹,哪些是右子樹。
也許全都是左子樹,也可能全部都是右子樹。

這邊可以藉由 Inorder 來判斷。
假設 Preorder 的第一個 element 是 r0,則在 Inorder 中,r0 之前的,就是左子樹;r0 之後的,就是右子樹。
跟據左子樹跟右子樹的這些 elements,就可以判斷在 Preorder 當中,哪些屬於左子樹,哪些是右子樹。

接著,左子樹跟右子樹又可以單獨拿出來看,成為新的樹,找到新的根。
然後就可以重複上述的步驟,用 recursive 的方式,找完所有 elements,
這時就可以畫出這整個 binary tree 了。

我們可以用一個例子來看:
Preorder: [0, 1, 3, 4, 2, 5]
Inorder: [3, 1, 4, 0, 2, 5]

從 Preorder 得知根是[0],從 Inorder 得知左子樹的 elements 是[3, 1, 4],右子樹是[2, 5]。
因此 Preorder 這邊的左子樹的 elements 是[1, 3, 4],右子樹是[2, 5]。

接著從 Preorder,新的左子樹得到根是[1],從 Inorder 得知左子樹的 elements 是[3],右子樹是[4]。
新的右子樹得到根是[2],從 Inorder 得知左子樹是[5]。
我們便可以從這些資訊畫出下面的 binary tree。

同理,Postorder 跟 Inorder 也可以畫出獨特的 binary tree,差別就是,根是位在 Postorder 的最後一個 element。

Like what you read? Give Gary Yeh a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.