Python文件解析：从文本文件构建树形结构

Question

我有一个缩进的文本文件，将用于构建一棵树。每行代表一个节点，缩进表示深度以及当前节点是其父节点的子节点。

例如，文件可能如下所示：

ROOT Node1 Node2 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块中，当我从每次递归调用返回时。

- MxLDevs

---

你需要编写大量代码来正确解析和验证它。你能使用XML吗？它的基本结构是一棵树。 - guax

很遗憾，这更像是一个递归练习而不是其他什么。虽然我认为这种问题可能很常见。 - MxLDevs

这可能是一个作业问题吗？如果是的话，添加作业标签是礼节。 - Mu Mind

不是，只是个人兴趣。已经有一段时间没有做递归了。 - MxLDevs

如果是这样，这实际上与Python无关。更多的是一种通用的算法思考。 - Santa

Answer 1

如果您不坚持使用递归，这也是可行的：

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
\t\tNode2
\t\t\tNode3
\t\t\t\tNode4
\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']

- pillmuncher

---

风格很棒。特别是“is_tab”的定义。 - Bunyk

不使用takewhile（更快且，我认为，更简洁）：for line in lines: body = line.lstrip('\t'); level = len(line) - len(body); stack[level:] = (body,)。 - Kirill Bulygin

这太干净了。 - aheze

Answer 2

主要问题是我认为引起了这个问题的“向前查看”。可以稍微缩短一下：

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）。更符合Python风格的做法是将它们作为某个解析器对象的成员。

- Mu Mind

---

@martineau：你说得对，我本意是在函数内将'inFile'替换为'source'，现已修复。 - Mu Mind

同时，我认为 last_line 参数总是作为 None 传递的 - 因此，在 while 循环之前可以将其设置为初始值为 source.readline().rstrip() 的局部变量（并删除检查它是否为 None 的代码）。 - martineau

@martineau：又说对了，已经进行了编辑。当我写这个的时候，我在尝试一些东西，不确定每次递归/返回是否对应于移动到下一行输入。既然我提到这是一个“缩短”的版本，我想我最好把所有的空气都挤出来，对吧？ - Mu Mind

Answer 3

我不会在这种情况下使用递归（好吧，也许如果我用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)

- Boaz Yaniv