Рекурсивная функция, которая печатает дерево

Question

У меня есть объект дерева:

a = <albero.Albero at 0x21fbc003cf8>

Этот метод:

a.f #print out a list of sons object
[<albero.Albero at 0x21fbc003cc0>]

a.id #print out the value of a
"03"

Я создал дерево, но теперь проблема в этом.Я хочу вернуть строку вывода следующим образом:

'''           05              
 _____________|_____________  
|             |             | 
02            04            06
|    _________|_________      
01  |     |     |   |   |     
    01    02    09  08  02    
         _|_                  
        |   |                 
        03  06                '''

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

'''04
| 
05
| 
01
| 
06
| 
03'''

для этого дерева я пытаюсь создать этот список:

['  80  ',' _|_  ','|   | ','70  90']

Есть идеи?

Answer 1

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

Fake Tree Node class для тестирования:

class Albero:
    def __init__(self,id,parent=None):
        self.id = id
        self.f = []
        if parent: parent.f.append(self)

n05  = Albero("05")
n02  = Albero("02",n05)
n04  = Albero("04",n05)
n06  = Albero("06",n05)
Albero("01",n02)
Albero("01",n04)
n02 = Albero("02",n04)
Albero("09",n04)
Albero("08",n04)
Albero("02",n04)
Albero("03",n02)
Albero("06",n02)

Рекурсивная функция treeLines () ожидает корневой узел в качестве первого параметра ифункция для получения идентификатора и дочерних узлов в качестве второго параметра.Это делает функцию универсальной и способной обрабатывать любой класс, имеющий отношение родитель-потомок к себе.
Функция treeText () использует результат treeLine () для построения одной строки с символом конца строки между каждой строкой.

def treeLines(node,getInfo):
    nodeId,nodeChildren = getInfo(node)
    subNodes   = [treeLines(child,getInfo) for child in nodeChildren]
    widths     = [ len(childText[0]) for childText in subNodes ]
    totalWidth = sum(widths) + 2*len(widths) - 1
    totalWidth = max(totalWidth,len(nodeId))
    nodeLine   = nodeId.center(totalWidth," ")
    result     = [nodeLine]
    if not nodeChildren: return result
    linksLine   = "  ".join("|".center(width," ") for width in widths)
    linksLine   = linksLine.center(totalWidth," ")
    leftIndent  = linksLine.index("|") + 1
    rightIndent = linksLine[::-1].index("|") + 1
    spanWidth   = totalWidth - leftIndent - rightIndent - 1
    leftSpan    = nodeLine.index(nodeId)-leftIndent+(len(nodeId)-1)//2
    rightSpan   = spanWidth - leftSpan   
    spanLine    = " "*leftIndent + "_"*leftSpan + "|" + "_"*rightSpan + " "*rightIndent
    if len(nodeChildren) > 1 : result.append(spanLine)
    result.append(linksLine)
    maxHeight   = max(len(subNode) for subNode in subNodes)
    subNodes    = [ subNode + [" "*len(subNode[0])]*(maxHeight-len(subNode)) for subNode in subNodes ]
    result     += ["  ".join([subNode[i] for subNode in subNodes]).center(totalWidth," ") for i in range(maxHeight) ]
    return result  

def treeText(node,getInfo): return "\n".join(treeLines(node,getInfo))

print( treeText(n05,lambda n:(n.id,n.f)) )

Печать:

                05                
  ______________|______________   
 |              |              |  
 02             04             06 
 |    __________|_________        
 01  |      |     |   |   |       
     01     02    09  08  02      
           _|_                    
          |   |                   
          03  06