3

所以，我有明显的蛮力算法，如下

int isSubtree (binTree *S, binTree *T)
{
    if (S == NULL)
        return 0;
    return (isEqual (S,T) || isSubtree (S->left, T) || isSubtree (S->right, T));
}

int isEqual (binTree *S, bintree *T)
{
    if (S==NULL && T==NULL)
        return 1;
    if (S==NULL || T==NULL)
        return 0;
    if (S->val == T->val)
        return isEqual(S->left,T->left) && isEqual (S->right,T->right);
    else
        return 0;
}

但这是 O(n²) 方法。

我有另一种方法，如下所示，是 O(n) 我们以中序方式遍历第一棵树并将其存储在数组中。然后我们遍历第二棵树并以有序的方式存储它。现在，如果第二个数组是第一个数组的子数组，我们继续并重复相同的过程来进行前序遍历。如果两个查询的结果都是 TRUE，则树是第一棵树的子树。否则，不会。

有人可以告诉我以下算法是否有效吗？

是否有针对此问题的空间优化解决方案？

注意：我需要两个数组，因为我存储了两个数组的遍历，无论如何我可以只使用一个数组吗？就像我会存储其中一棵树的中序遍历，然后在遍历另一棵树时使用该数组检查子数组条件。或者可能没有额外的空间，但 O(n) 时间复杂度？

注意：通过子数组，我的意思是元素应该连续出现，即

{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}
4

4 回答 4

1

摘要：考虑在每个节点中存储哈希和/或子树大小以加快搜索速度。您提出的算法已损坏。

您提出的算法 - 坏了？

如果我正确理解了您提出的替代算法，那么它就行不通。作为一个反例，请考虑：

  T          S
  x          x
 / \        / \
y   z      y   z
                \
                 q

T有中序遍历yxz，前序xyz。S有中序遍历yxzq，前序xyzq。

因此，尽管 T 不是有效匹配项（根据您的递归方法），但 T 的遍历被发现嵌入在 S 中。

在递归匹配过程中快速消除子树

我一直在按照 Karthikeyan 的建议进行思考——在每个节点上存储子树深度，因为它可以让你消除很多比较。当然，如果动态维护它也会使某些树操作更加昂贵 - 必须优先考虑那些或子树查找期间的额外命中。

存储子树元素的哈希是另一种可能性。什么是有意义的取决于与子树发现相比，树的结构和数据如何动态更新，以及从整体性能的角度来看是否更重要。

进一步阅读

无论如何，有很多关于此的现有问题，例如查找树是否是 other 的子树。哦 - 也发现了这个 -确定一棵二叉树是否是使用预排序和有序字符串的另一棵二叉树的子树- 这似乎支持我上面的逻辑，因为你说递归方法是正确的但很慢。

于 2013-07-22T05:16:42.840 回答
0

我们可以使用中序遍历和 DFS（在二叉树中，它简化为前序遍历）。现在首先使用 DFS，修改两棵树的数据结构，并在每个节点存储其下的子树的数量。之后为两棵树编写中序遍历，然后将字符串与 KMP 匹配。在 O(n+m)（两棵树中的 n 和 m- 个节点）中，我们可以找出不同的匹配。我们可以使用散列连接到带有 DFS 的修改后的图。在每次与 KMP 匹配时，我们可以比较两者的 DFS 修改图（在子树的数量上），如果它也匹配整个序列，则它是子树，否则我们去 KMP 的另一个匹配等等上。

在上面的例子中，在 DFS 之后修改的数据结构 fot 'T' 是 [x(2);y(0);z(0)] & for 'S' [x(3);y(0);z( 1);q(0)]。'T' 的顺序：yxz 'S' 的顺序：yxzq

我们得到匹配'yxz'。现在我们进入 DFS 修改后的结构。x 处不匹配；所以，“T”不是“S”的子树。

于 2013-12-28T04:37:16.557 回答
0

在数组 {2,3,5} 中，根可以是 2 或 3 或 5，因此您不能使用这样的数组来表示树。

如果 A 是 B 的子树（类似于您的代码），并假设leafs(x)从左到右是“树 x 的叶子节点”的数组，那么叶子（A）是叶子（B）的子串。

一旦你找到了上面的子字符串，检查从叶子到根的节点，以确保它真的是一个子树。

于 2013-12-28T06:09:37.293 回答
0

如何进行深度优先搜索并存储每个节点的子树节点数，并仅比较其节点数等于所讨论的另一棵树的父节点的子树。

于 2013-07-22T04:52:31.097 回答