Бинарное дерево, представленное вложенными скобками
Я новичок в python, я строю дерево, это мой код:
class BinaryTree():
def __init__(self, dado, left = None, right = None):
self.dado = dado
self.left = left
self.right = right
Я хочу сделать функцию для представления бинарного дерева, представлен вложенными скобками. Эта функция получает корень и показывает в одной строке структуру элементов. Например, дерево:
отображается как (1 (2 () ()) (3 () (4 () ()))).
В этом дереве корень дерева представлен крайними круглыми скобками, за которыми следуют круглые скобки, заключающие в себе левый дочерний элемент (2 () ()) корня, а затем скобки, заключающие в себе правый дочерний элемент (3 () ( 4 () ) ( ))) от корня. У левого узла нет детей ()(), а у правого узла есть дочерний элемент (4()()), и это тоже лист ()().
Я попытался создать функцию, но не смог оставить ее с ожидаемым результатом... результат моей функции выглядит следующим образом:
1
2
3
4
мой код, пытающийся создать функцию, был таким:
def show(node):
string = []
if not node:
return
print(node.dado)
show(node.left)
show(node.right)
Какая часть вашего кода может когда-либо печатать круглые скобки?
Ответы 3
Вы действительно должны использовать рекурсию для этого, но ваша попытка не добавляет скобок и выводит разрывы строк.
В базовом случае, когда узел равен None, строка должна быть "()". Когда узел не является None, это вопрос объединения рекурсивных результатов двух дочерних элементов с собственным значением узла.
Вот функция для этого:
def serialize(node):
if not node:
return "()"
return f"({node.dado} {serialize(node.left)} {serialize(node.right)})"
Вот как вы можете его использовать:
# Create tree that's used as example in the question
root = BinaryTree(1, BinaryTree(2), BinaryTree(3, None, BinaryTree(4)))
# Create the string for it
print(serialize(root)) # (1 (2 () ()) (3 () (4 () ())))
Вы уже реализовали обход дерева чтобы, и это хорошо. Вы пропустили две вещи:
- Что вы хотите напечатать, если узел равен нулю? -> пустые скобки
- Что вы хотите напечатать до и после каждого шага? -> скобки
Таким образом, ваша функция может выглядеть так:
def show(node):
if not node:
print("()", end="")
return
print(f"({node.dado} ", end="")
show(node.left)
print(" ", end="")
show(node.right)
print(")", end="")
Параметр конец для print предотвращает добавление символа новой строки в конце.
Еще одна вариация:
def show(node):
print(end='(')
if node:
print(node.dado, end=' ')
show(node.left)
print(end=' ')
show(node.right)
print(end=')')
не должно быть там, я уже организую код