search - 如何找到匹配的子树？

Question

我有一个大的二叉树，T.T“匹配”。T 的一些子树也将匹配。事实上，匹配的子树甚至不需要是完整的子树：它们也可以被截断。通过截断子树，我的意思是子树中的节点可能不会一直包含子节点——一些有子节点的节点可能会删除它们的子节点。

一个例子：见这个链接。由poem1、stanza1、stanza2、line3 表示的树是截断子树的示例。

确定一棵树是否匹配需要对整棵树进行计算。这不是进步的。

我到底是如何找到所有匹配项的？

Answer 1

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

听起来大致就像您要查找的内容（除了您也在原始图的所有子图上尝试此操作，这使其变得更加困难）。我真的不知道你是如何定义“匹配”（平等、图案、颜色协调、末端粘上会在撞击时点燃的化学物质？），所以这可能是一个完全不同的问题。