Блог

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

Например, файл может выглядеть как

КОРЕНЬ
 Узел 1
 Узел 2
 Node3
 Node4
 Node5
 Node6

Это указывает на то, что ROOT содержит три дочерних элемента: 1, 5 и 6, у Node1 есть один дочерний элемент: 2, а у Node2 есть один дочерний элемент: 3 и т.д.

Я придумал рекурсивный алгоритм и запрограммировал его, и он работает, но он какой-то уродливый и особенно грубо обрабатывает приведенный выше пример (при переходе от узла 4 к узлу 5)

В качестве основы для рекурсии используется «количество отступов», поэтому, если количество отступов = текущая глубина 1, я бы углубился на один уровень. Но это означает, что когда я читаю строку с меньшим количеством отступов, мне приходится возвращаться на один уровень за раз, каждый раз проверяя глубину.

Вот что у меня есть

 def _recurse_tree(node, parent, depth):
    tabs = 0
    
    while node:
        tabs = node.count("t")
        if tabs == depth:
            print "%s: %s" %(parent.strip(), node.strip())
        elif tabs == depth   1:
            node = _recurse_tree(node, prev, depth 1)
            tabs = node.count("t")
            
            #check if we have to surface some more
            if tabs == depth:
                print "%s: %s" %(parent.strip(), node.strip())
            else:
                return node
        else:
            return node
        
        prev = node
        node = inFile.readline().rstrip()
        
inFile = open("test.txt")
root = inFile.readline().rstrip()
node = inFile.readline().rstrip()
_recurse_tree(node, root, 1)
  

Прямо сейчас я просто распечатываю узлы, чтобы убедиться, что родительский узел корректен для каждой строки, но, может быть, есть более чистый способ сделать это? Особенно это касается блока elif, когда я возвращаюсь из каждого рекурсивного вызова.

Если вы не настаиваете на рекурсии, это тоже работает:

 from itertools import takewhile

is_tab = 't'.__eq__

def build_tree(lines):
    lines = iter(lines)
    stack = []
    for line in lines:
        indent = len(list(takewhile(is_tab, line)))
        stack[indent:] = [line.lstrip()]
        print stack

source = '''ROOT
tNode1
ttNode2
tttNode3
ttttNode4
tNode5
tNode6'''

build_tree(source.split('n'))
  

Результат:

 ['ROOT']
['ROOT', 'Node1']
['ROOT', 'Node1', 'Node2']
['ROOT', 'Node1', 'Node2', 'Node3']
['ROOT', 'Node1', 'Node2', 'Node3', 'Node4']
['ROOT', 'Node5']
['ROOT', 'Node6']
  

Большая проблема заключается в «предварительном просмотре», который, я думаю, вызвал рассматриваемое уродство. Его можно немного сократить:

 def _recurse_tree(parent, depth, source):
    last_line = source.readline().rstrip()
    while last_line:
        tabs = last_line.count('t')
        if tabs < depth:
            break
        node = last_line.strip()
        if tabs >= depth:
            if parent is not None:
                print "%s: %s" %(parent, node)
            last_line = _recurse_tree(node, tabs 1, source)
    return last_line

inFile = open("test.txt")
_recurse_tree(None, 0, inFile)
  

Поскольку мы говорим о рекурсии, я приложил все усилия, чтобы избежать любых глобальных переменных ( source и last_line ). Было бы более питонически сделать их членами в каком-либо объекте синтаксического анализа.

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

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

 import re

# *** Tree representation ***
class Node(object):
    def __init__(self, title):
        self.title = title
        self.parent = None
        self.children = []

    def add(self, child):
        self.children.append(child)
        child.parent = self

# *** Node insertion logic ***
class Inserter(object):
    def __init__(self, node, depth = 0):
        self.node = node
        self.depth = depth

    def __call__(self, title, depth):
        newNode = Node(title)
        if (depth > self.depth):
            self.node.add(newNode)
            self.depth = depth
        elif (depth == self.depth):
            self.node.parent.add(newNode)
        else:
            parent = self.node.parent
            for i in xrange(0, self.depth - depth):
                parent = parent.parent
            parent.add(newNode)
            self.depth = depth

        self.node = newNode

# *** File iteration logic ***
with open(r'tree.txt', 'r') as f:    
    tree = Node(f.readline().rstrip('n'))
    inserter = Inserter(tree)

    for line in f:
        line = line.rstrip('n')
        # note there's a bug with your original tab parsing code:
        # it would count all tabs in the string, not just the ones
        # at the beginning
        tabs = re.match('t*', line).group(0).count('t')
        title = line[tabs:]
        inserter(title, tabs)
  

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

 def print_tree(node, depth = 0):
    print '%s%s' % ('  ' * depth, node.title)
    for child in node.children:
        print_tree(child, depth   1)

print_tree(tree)