确定两个二叉树相等 [英] Determine if two binary trees are equal

问题描述

什么是有效的算法找出如果两个给出二叉树是平等的 - 在结构和内容

What would be the efficient algorithm to find if two given binary trees are equal - in structure and content?

推荐答案

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

It's a minor issue, but I'd adapt the earlier solution as follows...

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

原因在于错配很可能是共同的，而且是更好的检测（并停止比较）早期 - 进一步递归之前。当然，我假设短路和放大器;＆安培;运营商在这里。

The reason is that mismatches are likely to be common, and it is better to detect (and stop comparing) early - before recursing further. Of course, I'm assuming a short-circuit && operator here.

我还会指出，这是粉饰了一些问题，正确处理结构不同的树木，并与递归结束。基本上，我们需要有一些空检查t1.left等。如果一棵树有一个空。左，但对方不，你已经找到了一个结构上的差别。如果双方都有空。左，有没有什么区别，但你已经达到了叶 - 没有进一步的递归。只有这两个。左值都是非空你递归查询的子树。这同样适用，当然，对于.right

I'll also point out that this is glossing over some issues with handling structurally different trees correctly, and with ending the recursion. Basically, there need to be some null checks for t1.left etc. If one tree has a null .left but the other doesn't, you have found a structural difference. If both have null .left, there's no difference, but you have reached a leaf - don't recurse further. Only if both .left values are non-null do you recurse to check the subtree. The same applies, of course, for .right.

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

You could include checks for e.g. (t1.left == t2.left), but this only makes sense if subtrees can be physically shared (same data structure nodes) for the two trees. This check would be another way to avoid recursing where it is unnecessary - if t1.left and t2.left are the same physical node, you already know that those whole subtrees are identical.

C实现可能是...

A C implementation might be...

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));
}

修改在回答评论...

EDIT In response to a comment...

的运行时间使用这个一个完整的树比较，最简单的表述为O（n），其中n是一个有点树的大小。如果你愿意接受更复杂的约束，你可以得到一个较小的一个，如O（最小值（N1，N2）），其中n1和n2是树木的大小。

The running time for a full tree comparison using this is most simply stated as O(n) where n is kinda the size of a tree. If you're willing to accept a more complex bound you can get a smaller one such as O(minimum(n1, n2)) where n1 and n2 are the sizes of the trees.

的解释基本上是递归调用时，才进行（最多）一次左树中的每个节点，只发（最多），一次在正确的树中的每个节点。作为函数本身（不包括递归）仅规定至多工作的恒定量（没有环路），包括所有的递归调用的工作只能尽可能树越小倍的大小恒定。

The explanation is basically that the recursive call is only made (at most) once for each node in the left tree, and only made (at most) once for each node in the right tree. As the function itself (excluding recursions) only specifies at most a constant amount of work (there are no loops), the work including all recursive calls can only be as much as the size of the smaller tree times that constant.

您可以进一步分析，以获得更复杂，但更小的结合使用树木的交集的想法，但大O只是给出了一个上限 - 不一定是最低的上界。这也可能是不值得这样做的分析，除非你试图用这种建立一个更大的算法/数据结构的组成部分，并作为一个结果，你知道，有些属性将始终适用于那些树，这让您的更紧的束缚较大的算法。

You could analyse further to get a more complex but smaller bound using the idea of the intersection of the trees, but big O just gives an upper bound - not necessarily the lowest possible upper bound. It's probably not worthwhile doing that analysis unless you're trying to build a bigger algorithm/data structure with this as a component, and as a result you know that some property will always apply to those trees which may allow you a tighter bound for the larger algorithm.

以形成tigher结合的一种方式是考虑路径的套在两个树的节点。每个步骤可以是一个L（左子树）或R（右子树）。因此，根指定了一个空的路径。根的左子的右孩子是LR。定义一个函数路径（t）（数学上 - 该程序的一部分），以重新present所述一组有效路径成树。 - 一个路径为每个节点

One way to form a tigher bound is to consider the sets of paths to nodes in both trees. Each step is either an L (left subtree) or an R (right subtree). So the root is specified with an empty path. The right child of the left child of the root is "LR". Define a function "paths (T)" (mathematically - not part of the program) to represent the set of valid paths into a tree - one path for every node.

所以，我们可能有...

So we might have...

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

相同的路径规范适用于树木。而且每个递归始终遵循两个树相同的左/右链接。因此，递归访问在这些集合itersection的路径，以及最严格的约束，我们可以使用，这是那个路口的基数（仍与不变约束每递归调用工作）指定。

The same path specifications apply to both trees. And each recursion always follows the same left/right link for both trees. So the recursion visits the paths in the itersection of these sets, and the tightest bound we can specify using this is the cardinality of that intersection (still with the constant bound on work per recursive call).

有关树的结构上面，我们做递归以下路径...

For the tree structures above, we do recursions for the following paths...

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

因此​​，我们在这种情况下工作一定到至多三倍于tree_compare功能非递归工作的最大成本。

So our work in this case is bounded to at most three times the maximum cost of non-recursive work in the tree_compare function.

这通常是一种不必要的量的细节，但很明显的路径集的交集是至多一样大，在最小的原始树节点的数目。和是否在n中为O（n）是指节点的数目在一个原树或在两个节点的总和，这是比最低或我们的交点显然没有小。因此，O（n）是不是这样的紧约束，但它仍然是一个有效的上限，即使我们有点含糊其大小，我们在说什么。

This is normally an unnecessary amount of detail, but clearly the intersection of the path-sets is at most as large as the number of nodes in the smallest original tree. And whether the n in O(n) refers to the number of nodes in one original tree or to the sum of the nodes in both, this is clearly no smaller than either the minimum or our intersection. Therefore O(n) isn't such a tight bound, but it's still a valid upper bound, even if we're a bit vague which size we're talking about.

这篇关于确定两个二叉树相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！