Как сказать, включено ли дерево в другое?

Question

Я хотел бы создать алогритмо, которое позволяет мне сказать, включено ли дерево в другое. Благодаря этому сайту я управлял алгоритмом, который позволяет мне знать для двоичных деревьев, но я хотел бы обобщить его.

def isSubtree(T,S):
    '''
    function to say if a tree S is a subtree of another one, T
    '''
    # Base Case
    if S is None:
        return True

    if T is None:
        return True

    # Check the tree with root as current node
    if (areIdentical(T, S)):
        return True

    # IF the tree with root as current node doesn't match
    # then try left and right subtreee one by one
    return isSubtree(T.children, S) or isSubtree(T.children, S) # won't work because we have several children

def areIdentical(root1, root2):
    '''
    function to say if two roots are identical
    '''
    # Base Case
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False

    # Check if the data of both roots their and children are the same
    return (root1.data == root2.data and
            areIdentical(root1.children, root2.children)) # Here problem because it won't work for children

Ожидаемый результат

Например:

>>># first tree creation
>>>text = start becoming popular
>>>textSpacy = spacy_nlp(text1)
>>>treeText = nltk_spacy_tree(textSpacy)
>>>t = WordTree(treeText[0])

>>># second tree creation
>>>question = When did Beyonce start becoming popular?
>>>questionSpacy = spacy_nlp(question)
>>>treeQuestion = nltk_spacy_tree(questionSpacy)
>>>q = WordTree(treeQuestion[0])

>>># tree comparison
>>>isSubtree(t,q)
True

---

Если это может быть полезно, вот класс WordTree, который я использовал:

class WordTree:
    '''Tree for spaCy dependency parsing array'''
    def __init__(self, tree, is_subtree=False):
        """
        Construct a new 'WordTree' object.

        :param array: The array contening the dependency
        :param parent: The parent of the array if exists
        :return: returns nothing
        """
        self.parent = []
        self.children = []
        self.data = tree.label().split('_')[0] # the first element of the tree # We are going to add the synonyms as well.

        for subtree in tree:
            if type(subtree) == Tree:
                # Iterate through the depth of the subtree.
                t = WordTree(subtree, True)
                t.parent=tree.label().split('_')[0]
            elif type(subtree) == str:
                surface_form = subtree.split('_')[0]
                self.children.append(surface_form)

Очень хорошо работает с деревьями, созданными с помощью фраз Spacy.

question = "When did Beyonce start becoming popular?"
questionSpacy = spacy_nlp(question)
treeQuestion = nltk_spacy_tree(questionSpacy)
t = WordTree(treeQuestion[0])

Answer 1

Вы можете просто перебрать все дочерние элементы T, и если S является поддеревом любого из дочерних элементов T, тогда S является поддеревом T. Кроме того, вы должны вернуть False, когда T равно None, поскольку это означает, что вы уже находитесь на листе T, а S все еще не является поддеревом:

def isSubtree(T,S):
    if S is None:
        return True
    if T is None:
        return False
    if areIdentical(T, S):
        return True
    return any(isSubtree(c, S) for c in T.children)