Нужна помощь в завершении программы

Question

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

class Trie(object):
    """A Trie of TrieNodes. Trie has the following attributes:
     -- _root: a TrieNode; the root of this Trie.
    """

    def __init__(self):
        """Create an empty Trie."""

        self._root = TrieNode()

    def insert(self, word, data):
        """Insert the string 'word' with data 'data' into this Trie.

        -- word: the string with which the newly inserted 'data' will
           be associated.
        -- data: the data which will be stored in the TrieNode
           associated with the string 'word'.

        If there is a TrieNode associated with the word 'word' in this
        Trie, then _data of this TrieNode is updated to 'data'. Otherwise,
        enough new TrieNodes are created and inserted into this Trie, to
        create a TrieNode associated with 'word'.
        """

        raise Exception, "Implement me!"

    def find_node(self, word):
        """Return the TrieNode that corresponds to the string 'word'
        in this Trie. Return None if there is no such TrieNode in this
        Trie.
        -- word: a string; the TrieNode that corresponds to 'word'
        (if it exists) is returned.
        """

        raise Exception, "Implement me!"

Answer 1

Если все, что вам нужно, это подсказка, взгляните на запись в Википедии для набора , в которой рассказывается все, что вам нужно знать о том, как работают попытки.

Хорошо, вот еще один совет: каждый узел дерева будет содержать словарь, ключи которого являются символами, а значения - узлами дерева. Метод insert будет искать word[0], находить или создавать узел для этого символа, а затем, если len(word) больше 1, делать что-то с word[1:].

Answer 2

Если подсказок Роберта недостаточно, вот минимальная реализация Trie с двумя функциями, с которыми у вас возникли проблемы.

class Trie(object):
    def __init__(self, char='', data=None):
        self.children = []
        self.char = char
        self.data = data

    def get_child(self, char):
        for child in self.children:
            if child.char == char:
                return child

    def insert(self, key, data, node=None):
        if node is None:
            node = self
        if len(key) == 0:
            #key found
            node.data = data
            return node.data
        else:
            child = node.get_child(key[0])
            if child is None:
                child = Trie(key[0])
                node.children.append(child)
                return self.insert(key[1:], data, child)
            return self.insert(key[1:], data, child)

    def find(self, key, node=None):
        if node is None:
            node = self
        if len(key) == 0:
            #key found
            return node.data
        else:
            child = node.get_child(key[0])

            if child is None:
                return None
            return self.find(key[1:], child)

>>> tree = Trie()
>>> tree.insert('t', 't data')
>>> tree.insert('tr', 'tr data')
>>> print tree.find('t'), tree.find('tr')
t data tr data