查找一棵树是否是另一棵树的子树

Question

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

- sud03r

---

这棵树是否有某种排序方式？例如，它是二叉搜索树吗？ - Charles Ma

不是二叉搜索树。 - sud03r

抱歉，由于误读上面的评论，我将其重新标记为树（而不是二叉树），但当我意识到我的错误时，我又将其改回来了 :-) - David Johnstone

定义子树 - (T1(a)(b)) 是 (T2(T1(axy)(bz))) 的一个子树吗？还是你只考虑与 T1 的特定节点为根的树相等的子树，而不是其子图？ - Pete Kirkham

所有节点都存储字符数据，还是只有叶子节点？ - j_random_hacker

Answer 1

遍历T1。如果当前节点等于T2的根节点，则同时遍历这两棵树(T2和T1的当前子树)。比较当前节点。如果它们总是相等的，那么T2就是T1的子树。

- David Johnstone

---

抱歉挖出这么老的问题，但是问题中说数据中允许有重复。如果实际上存在重复，那么这个算法可能无法正确运行。我有什么遗漏吗？ - Aditya

@Aditya 如果你在每次失败的部分匹配后继续搜索，那么这个算法是正确的。 - John Dvorak

@Jan Dvorak，确实是正确的，但复杂度是多少？O(n^2)? 你会多次访问相同的节点。 - Michal

@MichalWegorek 只有 T2 的根节点与 T1 中的每个节点进行比较。只有在匹配时才会比较子树。只有当 T2 的根节点在 T1 中出现多次时，这种方法才是低效的。在这种特殊情况下，您有更好的算法吗？ - John Dvorak

[续前文] 如果你想要确保这些树是完全一样的，你需要遍历它们两次，一次是按照中序（左-中-右）的顺序，另一次则是按照前序或后序的顺序。 - Cristian Diaconescu

Answer 2

我建议使用一种算法，该算法使用预处理技术：

1）对T1树进行预处理，保留所有可能的子树根节点列表（缓存列表将有数百万条目）；

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

3）使用二分查找来定位所需的子树。您可以快速拒绝具有与T2节点数不相等（或深度不同）的节点数的子树。

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

- SadSido

Answer 3

如果已经给出了两个树的根节点，并且给出的节点类型相同，为什么仅仅确认T2的根节点在T1中是不够的？

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

谢谢。

- Nishith

Answer 4

如果你的树没有排序，我认为除了进行“暴力”搜索之外，别无选择：遍历树T1并检查是否到达与树T2的第一个节点匹配的节点。如果没有，继续遍历T1。如果是，则检查下一个节点是否匹配，直到找到T2的结束位置，在这种情况下，你就发现了：你的树T2确实是树T1的子树。

如果你知道T1每个节点的深度（从叶子到节点），你可以跳过那些深度不如所寻找子树的节点，这可以帮助你消除很多不必要的比较。假设T1和T2是平衡的，则树T1的总深度为20（2^20 > 1,000,000），树T2的深度为7（2^7 >100）。你只需要遍历T1的前13层（8192个节点——或者是否有14层和16384个节点？），便可跳过大约90%的T1...

然而，如果你所说的“子树”是指T2的叶节点也是T1的叶节点，那么你可以对T1进行第一次遍历，并计算每个节点的深度（从叶子到节点的距离），然后只检查具有与T2相同深度的子树。

- Pierre Arnaud

Answer 5

如果您的存储空间有限（即无法预先处理并以替代形式存储树），那么您可能无法做出比其他答案建议的暴力搜索更好的事情（遍历P1查找匹配P2的根，遍历两者以确定该节点是否实际上是匹配子树的根，如果它不匹配，则继续进行原始遍历）。这种搜索的时间复杂度为O(n * m)，其中n是P1的大小，m是P2的大小。根据您可用的树数据进行深度检查和其他潜在优化，这可能会被优化一些，但通常仍然是O(n * m)。根据您的具体情况，这可能是唯一合理的方法。

如果您的内存/存储没有限制，并且不介意有一些复杂性，我认为可以通过使用广义后缀树将其简化为最长公共子串问题来改进到O(n + m)。在这里中可以找到类似问题的一些讨论。也许等我有更多时间时，我会回来编辑并提供更具体的实现细节。

- iammichael

---

我将对树和查找进行序列化，以确定第二个字符串是否为第一个字符串的子串。在流行的编程语言中，我们有各种优化的子串查找算法可用。 - KRoy

Answer 6

我不确定我的想法是否正确。但是，供您参考。

1. 对 Tree 1 和 Tree 2 进行后序遍历，将其分别称为 P1 和 P2。
2. 比较 P1 和 P2。如果它们不同，那么这两棵树不是子树。退出。
3. 如果它们相同，或者P1包含在P2中，那么您可以决定哪个是子树。

- Guru

Answer 7

其中一种简单的方法是为树编写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变换进行高效压缩。并且可以使用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)时间内找到它是否是子集（考虑到排序数据中没有重复项）。

- KRoy

Answer 8

假设我们有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是子树。

- Amit Nag

Answer 9

我认为我们需要通过蛮力法去做，但是当你在T1中找到T2的根节点后，为什么还需要匹配树。 这不同于当我们不必找出树是否相同时。（那时我们只需要比较整棵树）

给定树T1和T2，指针而非值。

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

那么树T2是树T1的子树。

---

编辑：

只有在明确指出T2实际上是一个不同的树对象，并且我们需要找出T1中是否存在与T2相同的子树时，这种方法才行。

那么这种方法就行不通了。

我们别无选择，只能采用已经在这里讨论过的解决方案。

- Kumar Alok

Answer 10

我假设你的树是不可变的树，因此您永远不会更改任何子树（在Scheme术语中，您不会执行set-car！），而只是从叶子或现有树构建新树。

那么，我建议在每个节点（或子树）保留一个哈希码。用C语言来说，将tree-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 和 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 和 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 函数，您可以使用其他答案（或手册中提到的技术）。

- Basile Starynkevitch