查找树是否是其他树的子树

StackOverflow https://stackoverflow.com/questions/1017821

  •  06-07-2019
  •  | 
  •  

题

有两个二叉树T1和T2存储字符数据，允许重复。
 如何判断T2是否是T1的子树？ 。结果  T1有数百万个节点，T2有数百个节点。

有帮助吗？

解决方案

遍历T1。如果当前节点等于T2的根节点，则同时遍历两个树（T2和T1的当前子树）。比较当前节点。如果它们总是相等的，则T2是T1的子树。

其他提示

我建议使用预处理的算法：

1）预处理T1树，保留所有可能的子树根的列表（缓存列表将有数百万个条目）;

2）按照数据的降序对根的缓存列表进行排序，保存在root中。您可以选择更优雅的排序功能，例如，将字符树解析为字符串。

3）使用二进制搜索来定位必要的子树。您可以使用节点数快速拒绝子树，不等于T2节点数（或不同深度）。

请注意，步骤1）和2）必须只进行一次，然后您可以使用相同的预处理结果测试许多子树候选。

如果您的树没有以任何方式排序，我没有看到任何其他方式而不是进行强力搜索：遍历树 T1 并检查查看是否到达与树 T2 的第一个节点匹配的节点。如果没有，继续遍历 T1 。如果是这样，检查下一个节点是否匹配，直到找到 T2 的结尾，在这种情况下你有一个命中：你的树 T2 确实是 T1

如果您知道 T1 的每个节点的深度（从叶到节点），您可以跳过任何不像您要查找的子树那样深的节点。这可以帮助您消除大量不必要的比较。假设 T1 和 T2 很平衡，那么树 T1 的总深度为20（ 2 ** 20 ＆gt; 1,000,000 ）和树 T2 的深度为7（ 2 ** 7 ＆gt; 100 ）。您只需要走<13> T1 的13个图层（8192个节点 - 或者是14个图层和16384个节点？）并且可以跳过大约90个节点 T1 的百分比...

但是，如果通过子树表示 T2 的叶节点也是 T1 的叶节点，那么你可以先进行遍历 T1 并计算每个节点的深度（从叶到节点的距离），然后只检查与 T2 具有相同深度的子树。

如果你是内存/存储绑定（即不能以替代形式预先操作和存储树），你可能无法做出比其他一些答案建议的强力搜索更好的事情（遍历P1寻找P2的匹配根，遍历两者以确定该节点实际上是否是匹配子树的根，如果不匹配则继续原始遍历）。该搜索在O（n * m）中操作，其中n是P1的大小，m是P2的大小。根据您可用的树数据进行深度检查和其他可能的优化，这个人会稍微优化一下，但它通常仍然是O（n * m）。根据您的具体情况，这可能是唯一合理的方法。

如果你没有内存/存储限制并且不介意一点复杂性，我相信这可以通过减少到最长的常见子串问题借助广义后缀树。可以找到针对类似问题的一些讨论这里。也许当我有更多时间时，我会回来编辑一个实现的更多细节。

如果给出了两棵树的根，并且假设节点属于同一类型，那么为什么只是确定T2的根在T1中是不够的呢？

我假设“给定树T”指的是指向T的根和节点的数据类型的指针。

问候。

我不确定，我的想法是否正确。尽管如此，为了你的坚持。

  1. 在Tree 1＆amp ;;进行后续步行树2，称之为P1和P2。
  2. 比较P1＆amp; P2。如果他们不同。树不是子树。退出。
  3. 如果它们相同，或P2中包含P1。您可以决定哪一个是子树。

我认为我们需要蛮力，但为什么在T1中找到T2的根后需要匹配树。 它与我们不应该找到树是否相同时不一样。（然后我们只需要比较整棵树）

给你的是树T1和T2，指针，而不是值。

如果节点T2（它是指针）存在于T1树中。

然后树T2是T1的子树。

编辑：

只有当它通过对象明确表示T2实际上是一个不同的树时，我们需要找出T1中是否存在与T2相同的子树。

然后这不会起作用。

我们别无选择，只能选择此处讨论过的解决方案。

让我们说我们有T1作为父树，T2作为树，可能是T1的子树。请执行下列操作。做出的假设是T1和T2是二叉树，没有任何平衡因子。

1）在T1中搜索T2的根。如果没有找到，T2不是子树。在BT中搜索元素将花费O（n）时间。

2）如果找到元素，则从T2的节点根元素中找到T1的预订遍历。这将花费o（n）时间。也可以预先执行T2的遍历。将花费O（n）时间。预订遍历的结果可以存储到堆栈中。在堆栈中插入只需要O（1）。

3）如果两个堆栈的大小不相等，则T2不是子树。

4）从每个堆栈中弹出一个元素并检查是否相等。如果发生不匹配，则T2不是子树。

5）如果匹配T2的所有元素都是子树。

我假设你的树是不可变树所以你永远不会改变任何子树（你没有在Scheme用法中做 set-car！），但只是你是用树叶或现有树木建造新树木。

然后我建议保留在该节点的每个节点（或子树）哈希码。用C语言来说，将树-s声明为

 struct tree_st {
   const unsigned hash;
   const bool isleaf;
   union {
     const char*leafstring; // when isleaf is true
     struct { // when isleaf is false
        const struct tree_st* left;
        const struct tree_st* right;
     };
   };
 };

然后在构造时计算哈希值，当比较节点的相等性时，首先比较它们的哈希是否相等;大部分时间哈希码都不同（你不会费心比较内容）。

这是一个可能的叶子构造函数：

struct tree_st* make_leaf (const char*string) {
   assert (string != NULL);
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   t->hash = hash_of_string(string);
   t->isleaf = true;
   t->leafstring = string;
   return t;
}

计算哈希码的函数是

unsigned tree_hash(const struct tree_st *t) {
  return (t==NULL)?0:t->hash;
}

从两个子树构建节点的函数 sleft ＆amp; sright 是

struct tree_st*make_node (const struct tree_st* sleft,
                          const struct tree_st* sright) {
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   /// some hashing composition, e.g.
   unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
   t->hash = h;
   t->left = sleft;
   t->right = sright;
   return t;
 }

比较函数（两个树 tx ＆amp; ty ）利用了如果哈希码不同，则比较是不同的

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
  if (tx==ty) return true;
  if (tree_hash(tx) != tree_hash(ty)) return false;
  if (!tx || !ty) return false;
  if (tx->isleaf != ty->isleaf) return false;
  if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
  else return equal_tree(tx->left, ty->left) 
              && equal_tree(tx->right, ty->right);

}

大多数情况下， tree_hash（tx）！= tree_hash（ty）测试会成功，您无需递归。

了解散列消息。

一旦你有了这样一个有效的基于散列的 equal_tree 函数，你就可以使用其他答案（或手册）中提到的技术。

一种简单的方法是为树编写is_equal（）方法并执行以下操作，

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}

请注意，可以通过使用树的哈希码来优化is_equal（）。它可以通过将树的高度或子的数量或值的范围作为哈希码来以简单的方式完成。 

bool is_equal(TNode*other) {
    if(x != other->x) return false;
    if(height != other->height) return false;
    if(nchildren != other->nchildren) return false;
    if(hashcode() != other->hashcode()) return false;
    // do other checking for example check if the children are equal ..
}

当树类似于链表时，它将花费O（n）时间。我们也可以在选择要比较的孩子时使用一些启发式方法。

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    if(is_equal(other)) return true;
    if(left == NULL || right == NULL) {
          return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
    }
    if(left->nchildren < right->nchildren) { // find in smaller child tree first
          return (left->contains_subtree(other)) || right->contains_subtree(other);
    } else {
          return (right->contains_subtree(other)) || left->contains_subtree(other);
    }
}

另一种方法是将两个树序列化为字符串，并查找第二个字符串（从T2序列化）是否是第一个字符串的子字符串（从T1序列化）。

以下代码按预先序列进行序列化。

   void serialize(ostream&strm) {
            strm << x << '(';
            if(left)
                    left->serialize(strm);
            strm << ',';
            if(right)
                    right->serialize(strm);
            strm << ')';
    }

我们可以使用一些优化算法，例如， Knuth-Morris-Pratt算法找到（可能在O（n）时间内）子串的存在并最终查找树是否是其他的子树。

再次使用Burrows-Wheeler_transform可以有效地压缩字符串。并且可以 bzgrep 来搜索压缩数据中的子字符串。

另一种方法是按树的高度和数量对树中的子树进行排序。 

bool compare(TNode*other) {
    if(height != other->height)
        return height < other->height;

    return nchildren < other->nchildren;
}

请注意，将有O（n ^ 2）个子树。为了减少数量，我们可以根据高度使用一些范围。例如，我们只能对高度为1000到1500的子树感兴趣。

当生成排序数据时，可以在其中进行二进制搜索，并查找它是否是O（lg n）时间内的子集（考虑到排序数据中没有重复）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top