给定一个AVL树的PreOrder遍历。树是否是唯一的？

Question

我正在与AVL树一起工作。

我需要用散列标识任何给定的树，以构建散列，我正在考虑寻找树中所有元素的前序遍历，然后通过连接每个元素的散列来构建散列。

首先，我想确保没有重复的AVL树对于相同的预订字符串。尽管我还没有找到一个反例，但我真的不太确定。

任何帮助表示赞赏！

Answer 1

不同元素上的BST（二叉搜索树）由其前序遍历列表L唯一确定：这可以通过归纳显示。

事实上：

1. 根r必须L的第一元件
2. r的左子树必须包含小于r的所有元素，它的前序遍历为L的包含子列表这些元素：因此左子树是通过归纳唯一确定的。
3. 相同的R

这一结果也适用于一个AVL，因为它是一种特殊类型的BST的右子树。