#python #binary-search-tree #yield #recurrence
#python #двоичное дерево поиска #выход #повторение
Вопрос:
Я хотел бы получить значения из дерева в качестве генератора для перебора по ним. В этом случае yield
просто выдает мне единственное значение. Функция print_tree
работает как ожидалось — она показывает значения от наименьшего к наибольшему. Как получить аналогичный результат, но с перехватом их по одному? Это моя реализация BST:
class Node:
def __init__(self, element):
self.left = None
self.right = None
self.data = element
def add_element(self, element):
if self.data > element:
if self.left is None:
self.left = Node(element)
else:
self.left.add_element(element)
else:
if self.right is None:
self.right = Node(element)
else:
self.right.add_element(element)
def print_tree(self):
if self.left: self.left.print_tree()
print(self.data, end=' ')
if self.right: self.right.print_tree()
def get_values(self):
if self.left: self.left.get_values()
yield self.data
if self.right: self.right.get_values()
def get_structure(self):
return (self.left.get_structure() if self.left else None, self.data, self.right.get_structure() if self.right else None)
Код для тестирования:
from node import *
x = Node(3)
x.add_element(5)
x.add_element(1)
x.add_element(7)
print(x.get_structure()) #result: ((None, 1, None), 3, (None, 5, (None, 7, None)))
x.print_tree() #result: 1 3 5 7
z = x.get_values()
print(list(z)) #result: [3]
Не могли бы вы, пожалуйста, объяснить мне, где я допускаю ошибку и как я могу ее исправить?
Ответ №1:
Сначала вы выводите все элементы из левого поддерева, затем значение узла и, наконец, все элементы из правого поддерева
def get_values(self):
if self.left:
yield from self.left.get_values()
yield self.data
if self.right:
yield from self.right.get_values()