Я изучал структуру данных 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 предполагает, что нам нужно поместить дочерние элементы каждого узла в очередь поиска, но как я могу получить все дочерние элементы узла этого типа дерева?