检查两棵二叉搜索树是否相同

引言

二叉搜索树（BST）是计算机科学中的一种基本数据结构，可用于对数据进行排序和组织。检查两个树的相似性是 BST 上一项经常执行的操作。它是一种分层数据结构，由节点组成，每个节点最多有两个子节点：左子节点和右子节点。

BST 的主要特点是对于每个节点：

• 左子树中的所有元素都小于该节点的值。
• 右子树中的所有元素都大于该节点的值。

此属性保证了树中的信息以排序方式排列，从而促进了有效的搜索功能。

确定相同 BST 的方法

为了确定两个 BST 是否相同，我们必须同时遍历两棵树并比较对应的节点。如果我们发现树的结构有任何差异，或者对应节点的值不匹配，我们就认为这两棵树是不同的。反之，如果我们能够遍历两棵树而没有任何差异，我们就认为它们非常相似。

代码

输出

代码解释

Struct TreeNode： 在二叉搜索树中，此结构代表一个节点。它有两个指针，left 和 right，分别指向左子节点和右子节点，还有一个数据字段用于存储节点的值。

Function createNode： 负责使用提供的值创建新节点。它使用 malloc 为新节点分配内存，将 left 和 right 指针设置为 NULL，并将数据值设置为提供的值。然后返回一个指向新创建节点的指针。

Function areIdenticalTrees： 该函数接受两个 BST 的根节点作为参数，并返回一个整数，指示这两个二叉搜索树是否相同。它使用递归方法同时遍历两棵树并比较它们的节点。

• 如果两棵树都为空（root1 和 root2 都为 NULL），则返回 1，表示它们相同。
• 如果两棵树都不为空且当前节点具有相同的数据值，它会递归地检查左子树和右子树。如果两棵树中的所有对应节点都相同，则返回 1；否则返回 0。
• 如果一棵树为空而另一棵树不为空，则返回 0，表示这两棵树不相同。

Main function： 主函数中构建了两个二叉搜索树。

• root1 以 10 为根节点创建。它有两个子节点（5 和 15），左子节点（5）还有两个子节点（3 和 7）。
• Root2 的结构和节点值与 Root1 相同，创建方式也类似。

构建完树后，调用 areIdenticalTrees 函数，将两棵树的根节点作为参数传递，以确定树是否相同。根据结果输出一条消息。

结论

总而言之，比较两棵二叉搜索树的对应节点需要遍历两棵树以确定它们是否相同。可以使用递归方法有效地完成此任务。通过理解 BST 的特性并实践比较技术，我们可以一致地确定两棵二叉搜索树是否相同。