Как мне найти подходящее поддерево?

Question

У меня большое двоичное дерево, т. Т "совпадает". Некоторое количество поддеревьев T также будет соответствовать. Фактически, совпадающие поддеревья не обязательно должны быть полными поддеревьями: они также могут быть усечены. Под усеченным поддеревом я подразумеваю, что узлы в поддереве могут не содержать дочерние элементы полностью - некоторые узлы, у которых есть дочерние элементы, могут удалять своих дочерних элементов.

Пример: см. эту ссылку . Дерево, представленное как poem1, stanza1, stanza2, line3, является примером усеченного поддерева.

Чтобы определить, соответствует ли дерево, требуется выполнить вычисления для всего этого дерева. Это не прогрессивно.

Как, черт возьми, я нахожу все совпадения?

Answer 1

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

звучит примерно как то, что вы пытаетесь найти (за исключением того, что вы пробуете это также на всех подграфах исходного графика, что делает его еще сложнее). Я действительно не знаю, как вы определяете «совпадения» (равенство, рисунок, цветовая согласованность, палочки с химическими веществами на конце, которые загораются при ударе?), Так что это может быть совсем другая проблема.