有两个二叉树 T1 和 T2 存储字符数据，允许重复。
如何确定 T2 是否是 T1 的子树？.
T1 有数百万个节点，T2 有数百个节点。
问问题
12880 次
10 回答
18
穿越T1。如果当前节点等于 T2 的根节点，则同时遍历两棵树（T2 和 T1 的当前子树）。比较当前节点。如果它们总是相等，则 T2 是 T1 的子树。
于 2009-06-19T12:59:59.650 回答
3
我建议使用预处理的算法：
1）预处理T1树，保留所有可能的子树根的列表（缓存列表将有数百万个条目）；
2) 将缓存的根列表按数据的降序排序，保存在根中。您可以选择更优雅的排序功能，例如将字符树解析为字符串。
3) 使用二分查找来定位必要的子树。您可以快速拒绝节点数不等于 T2 节点数（或具有不同深度）的子树。
请注意，步骤 1) 和 2) 必须只执行一次，然后您可以使用相同的预处理结果测试许多子树候选者。
于 2009-06-19T13:06:45.550 回答
2
如果您的树没有以任何方式排序，除了进行蛮力搜索之外，我看不到任何其他方法：遍历树T1并检查您是否到达与树的第一个节点匹配的节点T2。如果没有，继续遍历T1。如果是这样，检查下一个节点是否匹配，直到找到 的结尾T2，在这种情况下，你有一个命中：你的树T2确实是 的子树T1。
如果您知道T1（从叶到节点）的每个单个节点的深度，则可以跳过任何不如您要查找的子树那么深的节点。这可以帮助您消除很多不必要的比较。这么说T1并且T2平衡良好，则树T1的总深度为 20 ( 2**20> 1,000,000)，树T2的深度为 7 ( 2**7> 100)。您只需要走 13 个第一层（T18192 个节点 - 还是 14 层和 16384 个节点？），并且能够跳过大约 90% 的T1...
但是，如果通过子树表示 的叶节点T2也是 的叶节点T1，那么您可以进行第一次遍历T1并计算每个节点的深度（从叶到节点的距离），然后只检查具有相同深度的子树作为T2.
于 2009-06-19T13:04:05.510 回答
2
如果您受内存/存储限制（即无法预先操作并以替代形式存储树），那么您可能无法比其他一些答案建议的蛮力搜索做得更好（遍历 P1 寻找匹配 P2 的根，遍历两者以确定该节点是否实际上是匹配子树的根，如果不匹配则继续原始遍历）。此搜索在 O(n * m) 中进行，其中 n 是 P1 的大小，m 是 P2 的大小。根据您可用的树数据，通过深度检查和其他潜在的优化，这个人被优化了一点，但它通常仍然是 O(n * m)。根据您的具体情况，这可能是唯一合理的方法。
如果您不受内存/存储限制并且不介意一点复杂性，我相信这可以通过在广义后缀树的帮助下减少到最长的公共子字符串问题来改进到 O(n + m) 。可以在此处找到针对类似问题的一些讨论。也许当我有更多时间时，我会回来编辑更多关于实现的细节。
于 2009-06-19T14:22:00.500 回答
2
如果给定两棵树的根，并且给定节点属于同一类型，那么为什么仅仅确定 T2 的根在 T1 中是不够的？
我假设“给定一棵树 T”意味着给定一个指向 T 根的指针和节点的数据类型。
问候。
于 2010-01-08T10:22:17.450 回答
1
我不确定，我的想法是否正确。尽管如此，对于您的个人而言。
- 在树 1 和树 2 中进行 postorder walk，称为 P1 和 P2。
- 比较 P1 和 P2。如果他们不同。树不是子树。出口。
- 如果它们相同，或者 P1 包含在 P2 中。您可以决定哪一个是子树。
于 2009-06-19T13:26:00.567 回答
0
我认为我们需要通过蛮力进行，但是为什么在 T1 中找到 T2 的根之后还需要匹配树。它与我们不应该查找树是否相同时不同。（那么我们只需要比较整棵树）
你得到的是树 T1 和 T2，指针，而不是值。
如果节点 T2（它是一个指针）存在于 T1 树中。
那么树 T2 是 T1 的子树。
编辑：
只有当它说T2实际上是一个不同的Tree by object wise时，我们需要找出T1中是否存在与T2相同的子树。
那么这将不起作用。
我们别无选择，只能选择这里已经讨论过的解决方案。
于 2012-09-25T15:37:30.883 回答
0
假设我们有 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是一个子树。
于 2015-07-19T09:25:48.100 回答
0
我假设您的树是不可变的树，因此您永远不会更改任何子树（在 Scheme 用语中您不会这样做set-car!），而只是您正在从叶子或现有树构建新树。
然后我建议在每个节点（或子树）中保留该节点的哈希码。在 C 语言中，将树声明为
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)测试会成功，您不必递归。
阅读散列consing。
一旦您拥有如此高效的基于哈希的equal_tree函数，您就可以使用其他答案（或手册）中提到的技术。
于 2015-07-19T09:31:44.327 回答
0
一种简单的方法是为树编写 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) 时间内）子字符串的存在，并最终确定一棵树是否是 other 的子树。
再次使用 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) 时间内查找它是否是子集（考虑到排序后的数据中没有重复）。
于 2016-04-01T18:11:42.153 回答