algorithm - 给定 AVL 树的 PreOrder 遍历。这棵树是独一无二的吗？

Question

我正在为一个类(class)使用 AVL 树。

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

首先，我想确保相同的预订字符串没有重复的 AVLtrees。虽然我还没有找到反例，但我真的不太确定。

感谢任何帮助!

Answer 1

不同元素上的 BST(二叉搜索树)由其前序遍历列表 L 唯一确定:这可以通过归纳法证明。

确实:

1. 根 r 必须是 L 的第一个元素。
2. r的左子树必须包含小于r的所有元素，其前序遍历是包含这些元素的L的子列表:因此左子树是唯一确定的，通过归纳。
3. r的右子树也一样

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