給定一個AVL樹的PreOrder遍歷。樹是否是唯一的？

Question

我正在與AVL樹一起工作。

我需要用散列標識任何給定的樹，以構建散列，我正在考慮尋找樹中所有元素的前序遍歷，然後通過連接每個元素的散列來構建散列。

首先，我想確保沒有重複的AVL樹對於相同的預訂字符串。儘管我還沒有找到一個反例，但我真的不太確定。

任何幫助表示讚賞！

Answer 1

不同元素上的BST（二叉搜索樹）由其前序遍歷列表L唯一確定：這可以通過歸納顯示。

事實上：

1. 根r必須L的第一元件
2. r的左子樹必須包含小於r的所有元素，它的前序遍歷爲L的包含子列表這些元素：因此左子樹是通過歸納唯一確定的。
3. 相同的R

這一結果也適用於一個AVL，因爲它是一種特殊類型的BST的右子樹。