如何遍历树结构？

Question

你喜欢用什么方法来遍历树形数据结构呢？因为在某些情况下，递归的方法可能效率不高。我现在使用的是像上面那样的生成器。你有什么建议可以让它更快吗？

def children(self):
    stack = [self.entities]
    while stack: 
        for e in stack.pop():
            yield e
            if e.entities:
                stack.append(e.entities) 

这里有一些测试数据。第一个是递归方法，第二个是使用生成器的方法：

s = time.time()
for i in range(100000):
    e.inc_counter()
print time.time() - s

s = time.time()
for i in range(100000):
    for e in e.children():
        e.inc_counter_s()
print time.time() - s

结果：

0.416000127792
0.298999786377

测试代码：

import random

class Entity():
    def __init__(self, name):
        self.entities = []
        self.name = name
        self.counter = 1
        self.depth = 0

    def add_entity(self, e):
        e.depth = self.depth + 1
        self.entities.append(e)

    def inc_counter_r(self):
        for e in self.entities:
            e.counter += 1
            e.inc_counter_r()

    def children(self):
        stack = [self.entities]
        while stack:
            for e in stack.pop():
                yield e
                if e.entities:
                    stack.append(e.entities)

root = Entity("main")
def fill_node(root, max_depth):
    if root.depth <= max_depth:
        for i in range(random.randint(10, 15)):
            e = Entity("node_%s_%s" % (root.depth, i))
            root.add_entity(e)
            fill_node(e, max_depth)
fill_node(root, 3)

import time
s = time.time()
for i in range(100):
    root.inc_counter_r()
print "recursive:", time.time() - s

s = time.time()
for i in range(100):
    for e in root.children():
        e.counter += 1
print "generator:",  time.time() - s

Answer 1

递归函数调用并不是特别低效，这其实是个老掉牙的编程误区。（如果实现得不好，确实可能会比必要的开销大，但说它“特别低效”就是错的。）

记住：不要过早地进行优化，绝对不要在没有先进行性能测试的情况下进行优化。

Answer 2

除非你的树结构非常大，或者你对速度有很高的要求，否则我会选择递归的方法。这样写起来更简单，读起来也更容易。

Answer 3

我想不出有什么大的算法改进，但你可以做一个简单的小优化，就是把经常调用的方法（比如 stack.append 和 stack.pop）绑定到局部变量上（这样可以省去查字典的时间）。

def children(self):
    stack = [self.entities]
    push = stack.append
    pop = stack.pop
    while stack: 
        for e in pop():
            yield e
            if e.entities:
                push(e.entities)

根据我的测试，这样可以提高大约15%的速度（我用100次遍历一个深度为8、每个节点有4个子节点的树，得到了下面的时间记录：）

children     :  5.53942348004
children_bind:  4.77636131253

虽然提升不算大，但如果速度很重要的话，做这个优化还是值得的。