Обход BFS дерева дерева связанных списков в Python - PullRequest
1 голос
/ 16 июня 2019

Я изучал структуру данных trie в соответствии с книгой Кенда Д. Ли «Структуры данных и алгоритмы с Python». Там три реализованы с использованием двух указателей внутри каждого узла дерева: указатели follows и next (как показано на на этом рисунке , указатель follows выделен желтым, а next указатель выделен красным цветом).

И я успешно реализовал эту структуру:

class Trie:
    @staticmethod
    def __insert(node, item):
        # Recursive insert function
        # If the key is empty, return None as the empty node.
        if not item:
            node = None
        elif node is None:
            node = Trie.TreeNode(item[0])
            node.follows = Trie.__insert(node.follows, item[1:])
        elif item[0] == node.item:
            node.follows = Trie.__insert(node.follows, item[1:])
        else:
            node.next = Trie.__insert(node.next, item)
        return node

    @staticmethod
    def __contains(node, item):
        # Recursive search function
        if not item:
            return True
        if node is None:
            return False
        if item[0] == node.item[0]:
            return Trie.__contains(node.follows, item[1:])
        return Trie.__contains(node.next, item)


    class TreeNode:
        def __init__(self, item, nxt=None, follows=None):
            self.item = item
            self.next = nxt
            self.follows = follows

    def __init__(self):
        self.start = None

    def insert(self, item):
        self.start = Trie.__insert(self.start, item)

    def __contains__(self, item):
        return Trie.__contains(self.start, item)

Вопрос в том, как я могу реализовать алгоритм обхода BFS для этого дерева? Стандартный алгоритм BFS предполагает, что нам нужно поместить дочерние элементы каждого узла в очередь поиска, но как я могу получить все дочерние элементы узла этого типа дерева?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...