給定乙個完整二叉樹的預排序遍歷序列，你如何繪製樹 50？

我之所以畫不出來，是因為我不知道什麼是“完整”的二叉樹！

第一種在樓上畫的方法根本不是乙個完整的二叉樹。

乙個完整的二叉樹的左右子樹之間的高度差不能大於1，左邊子樹的高度不能小於右邊子樹的高度。

繪製方法如下：先計算節點數，再計算樹的高度（層數），然後直接畫出來。

第乙個節點必須是根節點，其左右子樹（除去底層）必須是完整的二叉樹。

在此基礎上，計算出左右二叉樹中的節點數，然後將剩餘的節點數分配給左右子樹。

依此類推，直到所有節點都用完。

有必要確定二叉樹結構中序數遍歷的順序。

在給出中間順序遍歷序列後，至少應該給出前序或後序來確定乙個雙管齊下的樹。

如果沒有中間階，即使有預序和後序，也無法確定二叉樹結構。

反對上樓，我可以畫出 n n 個具有不同結構的完整二叉樹，只有你的 1,2,3,4,5,6。

可以繪製，因為“完全”二叉樹。

不能畫畫，因為我不確定。

前階、中階和二階至少 2 個。

預訂單遍歷的節點序列為：befcgdh; 中間階遍歷的節點序列為：febgchd; 後序遍歷的節點序列為：feghdcb。

預排序遍歷首先訪問根節點，然後遍歷左側子樹，最後遍歷右側子樹; 順序遍歷首先遍歷左邊的子樹，然後訪問根節點，最後遍歷右邊的子樹; 順序遍歷先向左，再向右，再遍歷根，即先遍歷左邊的子樹，再遍歷右邊的子樹，最後訪問根節點。

fdbacegihj 的預購遍歷

中間階遍歷 abcdefhijg

Acbedhjigf 的後續遍歷

以下序列是 DCBA。

詳細說明如下：預序列的順序為根、左、右，序列的第乙個ABCD必須是根節點，A是根節點。

中間序列的順序是左、根、右，因為A是根節點，所以DCB在A的左邊，A的右邊沒有節點，B是DCB三個節點的根。

預序列為中間的左、右，根節點為a; 中間序列為左-中-右，左子樹為BCD; 二叉樹按照遍歷序列的規則排列，後階遍歷為DCBA。

原句應該是這樣的：一棵樹的後根的遍歷與樹對應的二叉樹的中位數遍歷相同。 由於將樹轉換為二叉樹後沒有正確的子樹，因此最後訪問樹的根節點。

先猜垂直根遍歷、中間根遍歷和後根遍歷。

預購遍歷、中階遍歷和後序遍歷。

是說同一件事的兩種方式。 二叉樹的前體遍歷序列與對應二叉樹的遍歷序列相同，但有乙個例外：二叉樹的每個節點只有乙個右子樹，即退化右偏的線性序列。

後遍歷是dgebhfca。

預購遍歷的第乙個節點是根節點，從預序遍歷中可以看出，a是根節點。 按中間順序遍歷的根節點前面的節點都是左子樹的節點，所以左子樹上的節點是dbge。

刪除根節點和左側子樹節點，並將右側子編號節點設定為 chf。 預序遍歷的第二個節點是 b，2 知道 b 是左子樹節點，所以 b 是左子樹的根節點。

在二叉樹中，找到順序遍歷，先向左遍歷，然後向右遍歷，然後再遍歷根，即先遍歷左子樹，然後遍歷右子樹，最後遍歷根節點。 那麼二叉樹的後階遍歷是 dgebhfca。

與以下兩個二叉樹一樣，前序遍歷序列為 ab，後序遍歷序列為 ba，因此無法唯一確定。 a a

b b 一般情況下，如果二叉樹中存在 1 階節點，則不能根據前階和後階遍歷序列唯一確定二叉樹。

這是因為相同的預購遍歷和後序遍歷序列可以對應不同的二叉樹。

例如，如果已知二叉樹的預序遍歷序列和後序遍歷序列分別為 abc 和 cba，則以下四個二叉樹滿足要求：

a a a a

b b b b

c c c c

先例：a b c d e f g h i 中階：c b e d a g h f j i 確定根是 a，c b e d 在 a 的左子樹上，g h f j i 在 a 的右子樹上。

先例：b c d e

中間順序：c b e d

確保 b 是根，c 是 b 的左子子，e d 在 b 的右子樹上。

先例：d e

中階：e d

確定 d 是根，e 是 d 的左子項。

先例：f g h i j

中階：g h f j i

確保 f 是根，g h 位於 f 的左側子樹上，j i 位於 f 的右側子樹上。

先例：g h

中階：g h

確定 g 是根，h 是 g 的右子項。

先例：i j

中階：j i

確保 i 是根，j 是 i 的左子項。

綜上所述，樹的結構如下所示：

ab fc d g i

e h j 後遍歷序列： c e d b h g j i f a