Бинарное дерево, представленное вложенными скобками

Я новичок в python, я строю дерево, это мой код:

class BinaryTree():
    def __init__(self, dado, left = None, right = None):
        self.dado = dado
        self.left = left
        self.right = right

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

enter image description here

отображается как (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)  

не должно быть там, я уже организую код

Josue Costa 09.04.2022 21:57

Какая часть вашего кода может когда-либо печатать круглые скобки?

Karl Knechtel 09.04.2022 22:14
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
1
2
26
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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 () ())))
Ответ принят как подходящий

Вы уже реализовали обход дерева чтобы, и это хорошо. Вы пропустили две вещи:

  1. Что вы хотите напечатать, если узел равен нулю? -> пустые скобки
  2. Что вы хотите напечатать до и после каждого шага? -> скобки

Таким образом, ваша функция может выглядеть так:

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=')')

Другие вопросы по теме