AVL树operator==重载实现：按元素集合判定相等而非结构一致

原有代码的问题 #

你之前实现的identicalTrees是树结构完全匹配+节点值完全一致的全等判断，只会把结构、节点位置、值完全一样的两棵树判定为相等，不符合「元素集合一致即相等」的需求。比如插入顺序6、8和8、6的两棵AVL树结构不同，这个函数会直接返回false，和预期结果相悖。

迭代器实现的效率说明 #

如果你实现的是AVL树的中序遍历迭代器，用迭代器做相等判断的效率是所有可行方案里最高的一档：

• 时间复杂度为O(n)，和其他遍历方案的渐近复杂度完全一致，没有冗余计算
• 空间复杂度仅为O(log n)（迭代器内部维护的遍历栈大小，和AVL树的树高正相关），远低于哈希表比对、拷贝元素到数组再比对这类需要O(n)额外空间的方案
• 核心依据是二叉搜索树的基本性质：AVL树的中序遍历结果一定是严格升序的有序序列，包含相同元素集合的两棵AVL树，中序遍历输出的序列必然完全相同；反过来中序序列完全一致的两棵AVL树，元素集合也一定完全匹配，和树的具体节点结构无关。

迭代器比对的正确实现方式 #

首先确认你的迭代器满足这几个基本要求：

• 支持获取指向树中最小元素的起始迭代器（即begin()接口）
• 支持获取标识遍历完成的尾后迭代器（即end()接口）
• 支持自增操作，移动到中序遍历的下一个元素
• 支持解引用操作，获取当前迭代器指向的元素值
• 支持相等/不等判断，确认两个迭代器是否指向同一位置

不需要提前把两棵树的元素全量拷贝到其他容器，直接用双迭代器同步遍历、边遍历边比对即可，参考实现如下：

bool operator==(const AVLTree& other) const {
    auto it_a = begin();
    auto it_b = other.begin();
    const auto end_a = end();
    const auto end_b = other.end();

    // 同步遍历两个有序序列，逐位比对元素
    while (it_a != end_a && it_b != end_b) {
        if (*it_a != *it_b) {
            return false;
        }
        ++it_a;
        ++it_b;
    }

    // 必须确认两个序列同时遍历完成，避免两棵树元素数量不同的情况
    return it_a == end_a && it_b == end_b;
}

这个实现可以完全满足你的判定需求：插入顺序6、8和8、6的两棵AVL树，中序遍历结果都是[6, 8]，比对时会逐位匹配、同时走到尾后迭代器，最终返回true。

注意事项 #

• 如果你的迭代器不是中序遍历实现（比如前序、后序、层序遍历），不能直接用这个方案——非中序的遍历结果会受树结构影响，同元素不同结构的树遍历结果不一致，会导致判定错误。
• 不要用“把一棵树元素全存入哈希表，再遍历另一棵树查表”的方案，这类方案不仅有哈希函数的常数开销，还需要额外O(n)的空间存储哈希表，实际运行效率远低于中序同步遍历的方案。

内容的提问来源于stack exchange，提问作者Olivia22