20

找出两个给定的二叉树是否在结构和内容上相等的有效算法是什么？

4

7 回答 7

24

这是一个小问题，但我会按如下方式调整早期的解决方案......

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

原因是不匹配可能很常见，最好在进一步递归之前尽早检测（并停止比较）。当然，我假设这里有一个短路 && 运算符。

我还要指出，这掩盖了正确处理结构不同的树以及结束递归的一些问题。基本上，需要对 t1.left 等进行一些空值检查。如果一棵树有空值 .left 而另一棵树没有，则您发现了结构上的差异。如果两者都具有 null .left，则没有区别，但您已经到达叶子 - 不要进一步递归。只有当两个 .left 值都不为空时，您才会递归检查子树。当然，这同样适用于 .right。

您可以包括对例如 (t1.left == t2.left) 的检查，但这仅在两个树可以物理共享子树（相同的数据结构节点）时才有意义。此检查将是另一种避免在不必要的地方递归的方法 - 如果 t1.left 和 t2.left 是同一个物理节点，您已经知道这些整个子树是相同的。

AC 实施可能是...

bool tree_compare (const node* t1, const node* t2)
{
  // Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  // Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  // Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

编辑回应评论......

使用它进行完整树比较的运行时间最简单地表示为 O(n)，其中 n 有点像树的大小。如果您愿意接受更复杂的界限，您可以获得更小的界限，例如 O(minimum(n1, n2)) 其中 n1 和 n2 是树的大小。

解释基本上是递归调用只对左树中的每个节点进行一次（最多）一次，并且对右树中的每个节点只进行一次（最多）一次。由于函数本身（不包括递归）最多只指定一个恒定的工作量（没有循环），包括所有递归调用的工作只能是较小树的大小乘以该常数。

您可以使用树的交叉点的想法进一步分析以获得更复杂但更小的界限，但大 O 只是给出一个上限 - 不一定是最低可能的上限。除非您尝试将其作为组件构建更大的算法/数据结构，否则可能不值得进行该分析，因此您知道某些属性将始终应用于那些可能使您对更大的算法。

形成更紧密界限的一种方法是考虑到两棵树中节点的路径集。每个步骤要么是 L（左子树），要么是 R（右子树）。所以根是用空路径指定的。根的左孩子的右孩子是“LR”。定义一个函数“paths (T)”（数学上 - 不是程序的一部分）来表示一组有效路径到树中 - 每个节点都有一个路径。

所以我们可能...

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

相同的路径规范适用于两棵树。并且每个递归始终遵循两棵树的相同左/右链接。因此递归访问这些集合的迭代部分中的路径，我们可以使用它指定的最严格的界限是该交集的基数（仍然具有每个递归调用的工作恒定界限）。

对于上面的树结构，我们对以下路径进行递归......

paths(t1) intersection paths(t2) = { "", "L", "R" }

因此，我们在这种情况下的工作最多限制为 tree_compare 函数中非递归工作的最大成本的三倍。

这通常是不必要的细节量，但显然路径集的交集最多与最小原始树中的节点数一样大。并且无论 O(n) 中的 n 是指一棵原始树中的节点数还是两者中的节点之和，这显然不小于最小值或我们的交集。因此 O(n) 不是一个严格的界限，但它仍然是一个有效的上限，即使我们有点模糊我们正在谈论的大小。

于 2009-09-28T13:46:18.463 回答
4

模堆栈溢出，类似于

eq(t1, t2) =
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)

（这概括为所有树结构代数数据类型的相等谓词 - 对于任何结构化数据，检查其每个子部分是否等于每个其他子部分。）

于 2009-09-27T05:23:57.950 回答
3

我们还可以进行任何两种遍历（前序、后序或中序），然后比较两棵树的结果。如果它们相同，我们可以确定它们的等价性。

于 2012-08-31T05:45:19.030 回答
1

您可能想要完成的更通用的术语是graph isomorphism。在该页面上有一些算法可以做到这一点。

于 2009-09-27T05:07:41.083 回答
1

因为这是一个已证明的事实 - 只要我们有以下内容，就可以重新创建二叉树：

  1. 在有序遍历中遇到的节点序列。
  2. 在前序或后序遍历中遇到的节点序列

如果两棵二叉树具有相同的中序和 [pre-order OR post-order] 序列，那么它们在结构和值方面应该相等。

每次遍历都是 O(n) 操作。总共进行了 4 次遍历，并比较了相同类型的遍历的结果。O(n) * 4 + 2 => O(n) 因此，时间复杂度的总顺序为 O(n)

于 2013-09-17T22:48:26.373 回答
0

我会写如下。以下代码适用于大多数函数式语言，如果您的数据类型是可散列的（例如，不是字典或列表），甚至在 python 中：

  • 拓扑等式（结构相同，即Tree(1,Tree(2,3))==Tree(Tree(2,3),1)）：

    tree1==tree2方法set(tree1.children)==set(tree2.children)

  • 有序相等：

    tree1==tree2方法tree1.children==tree2.children

（Tree.children 是一个有序的孩子列表）

您不需要处理基本情况（叶子），因为已经为它们定义了相等性。

于 2011-10-12T01:32:52.847 回答
0 
bool identical(node* root1,node* root2){
    if(root1 == NULL && root2 == NULL)
        return true;
    if(root1==NULL && root2!=NULL || root1!=NULL && root2 == NULL)
        return false;
    if(root1->data == root2->data){
        bool lIdetical = identical(root1->left,root2->left);
        if(!lIdentical)
            return false;
        bool rIdentical = identical(root1->right,root2->identical);
        return lIdentical && rIdentical;
    }
    else{
        printf("data1:%d vs data2:%d",root1->data,root2->data);
        return false;
    }
}

我不知道这是否是最有效的，但我认为这很有效。

于 2020-12-01T06:19:58.930 回答