Алгоритм создания чистого __str__ метода для дерева

Question

У меня есть класс Tree, который состоит из Node объектов. Каждый Node имеет следующие экземпляры экземпляров:

• name: строковое имя узла
• depth: int глубины узла в дереве (rootимеет глубину 0)
• parent: ссылка на родительский объект Node (родительский корень None)
• children: список всех дочерних объектов Node (листьяесть пустой список)

Класс Node также имеет метод get_ancenstors(), который возвращает список Node s в пути от родительского элемента Node к корню. ,

Дерево построено с использованием рекурсивной функции и имеет следующие переменные экземпляра:

• root: ссылка на корень Node
• leaves: список всех листов Node s

Класс Tree имеет метод dfs(), который выполняет первый поиск / обход дерева по глубине и выдает каждый Node посещенных. Он также имеет метод __str__() как таковой:

def __str__(self):
    string = ''
    for dir in self.dfs(self.root):
        # TODO: Create branches as '|-' 
        branches = ('  ' * (dir.depth))
        string += f'{branches}{dir.name}\n'
    return string

, который выдает результат:

Dir 1
  Dir 2
    Dir 3
  Dir 4
    Dir 5
      Dir 6
      Dir 7
    Dir 8
  Dir 9
    Dir 10

Вместо этого я хочу визуально более чистую, но более сложную реализацию этого __str__() метод, который производит вывод, подобный этому:

Dir 1
|--- Dir 2
|    |--- Dir 3
|
|--- Dir 4
|    |--- Dir 5
|    |    |--- Dir 6
|    |    |--- Dir 7
|    |
|    |--- Dir 8
|
|--- Dir 9
     |--- Dir 10
     |--- Dir 11
          |--- Dir 12

Может кто-нибудь помочь с логикой, стоящей за этим?

Answer 1

Можно создать рекурсивный генератор, который выдает полную строку для каждого дочернего элемента. Затем в __str__ вы можете просто использовать str.join:

class Tree:
   ...
   def to_dir(self, d = 0, flag=True):
      if flag:
        yield self.name if not d else '|'+"|".join(["\t"]*(d-1))+f'{"|"*(bool(d-1))}--- {self.name}'
      else:
         yield "".join(["\t"]*(d-1))+f'{"|"*(not d)}{"|"*(bool(d))}--- {self.name}'
      for i, a in enumerate(self.children):
         yield from a.to_dir(d=d+1, flag = falg)
   def __str__(self):
      return '\n'.join(self.to_dir())

---

Пример:

class Tree:
   def __init__(self, n, c):
      self.name, self.children = n, c
   def to_dir(self, d = 0, flag=True): 
      if flag:
         yield self.name if not d else '|'+"|".join(["\t"]*(d-1))+f'{"|"*(bool(d-1))}--- {self.name}'
      else:
         yield "".join(["\t"]*(d-1))+f'{"|"*(not d)}{"|"*(bool(d))}--- {self.name}'
      for i, a in enumerate(self.children):
         yield from a.to_dir(d=d+1, flag=False if not flag else i != len(self.children)-1)
   def __str__(self):
      return '\n'.join(self.to_dir())

t = Tree('Dir 1', [Tree('Dir 2', [Tree('Dir 5', [])]), Tree('Dir 3', []), Tree('Dir 4', [Tree('Dir 6', [Tree('Dir 7', [])])])])

Выход:

Dir 1
|--- Dir 2
       |--- Dir 5
|--- Dir 3
|--- Dir 4
       |--- Dir 6
              |--- Dir 7

Answer 2

Используйте следующее решение со специальной логикой форматирования:

def __str__(self):
    string = ''
    for dir in self.dfs(self.root):
        branches, depth = '', dir.depth
        if depth > 0:
            branches = '|--- '  # initial (closest) dashed block
            branches = '|    ' * (depth - 1) + branches
        string += f'{branches}{dir.name}\n'
    return string

---

Упрощенный тестовый пример для демонстрации:

from collections import namedtuple

Node = namedtuple('Node', 'name depth')
dfs = [Node(f'Dir{i+1}', depth=i) for i in range(4)]

def n__str__(dfs):
    string = ''
    for dir in dfs:
        branches, depth = '', dir.depth
        if depth > 0:
            branches = '|--- '  # initial (closest) dashed block
            branches = '|    ' * (depth - 1) + branches
        string += f'{branches}{dir.name}\n'
    return string

print(n__str__(dfs))

Вывод:

Dir1
|--- Dir2
|    |--- Dir3
|    |    |--- Dir4