摘要：前序輸出從這一路下來，有兩個是正確的，如果先判斷要遍歷的節點是否已經遍歷過的話，那么就走不通了，所以應該允許，點到就記一次輸出，再來判斷是否能繼續往下走。

代碼來自：pickle and cPickle – Python object serialization
首先樹的結構，如圖

import pickle

class Node(object):
    """A simple digraph where each node knows about the other nodes
    it leads to.
    """
    def __init__(self, name):
        self.name = name
        self.connections = []
        return

    def add_edge(self, node):
        "Create an edge between this node and the other."
        self.connections.append(node)
        return

    def __iter__(self):
        return iter(self.connections)

def preorder_traversal(root, seen=None, parent=None):
    """Generator function to yield the edges via a preorder traversal."""
    if seen is None:
        seen = set()
    yield (parent, root)
    if root in seen:
        return
    seen.add(root)
    for node in root:
        for (parent, subnode) in preorder_traversal(node, seen, root):
            yield (parent, subnode)
    return

def show_edges(root):
    "Print all of the edges in the graph."
    for parent, child in preorder_traversal(root):
        if not parent:
            continue
        print "%5s -> %2s (%s)" % (parent.name, child.name, id(child))

# Set up the nodes.
root = Node("root")
a = Node("a")
b = Node("b")
c = Node("c")

# Add edges between them.
root.add_edge(a)
root.add_edge(b)
a.add_edge(b)
b.add_edge(a)
b.add_edge(c)
a.add_edge(a)

print "ORIGINAL GRAPH:"
show_edges(root)

# Pickle and unpickle the graph to create
# a new set of nodes.
dumped = pickle.dumps(root)
reloaded = pickle.loads(dumped)

print
print "RELOADED GRAPH:"
show_edges(reloaded)

輸出結果：

$ python pickle_cycle.py

ORIGINAL GRAPH:
 root ->  a (4299721744)
    a ->  b (4299721808)
    b ->  a (4299721744)
    b ->  c (4299721872)
    a ->  a (4299721744)
 root ->  b (4299721808)

RELOADED GRAPH:
 root ->  a (4299722000)
    a ->  b (4299722064)
    b ->  a (4299722000)
    b ->  c (4299722128)
    a ->  a (4299722000)
 root ->  b (4299722064)

其中preorder_traversal是生成器。這里記錄下生成器方法的每一步的意思。

# root 要遍歷的根節點
# seen 保存遍歷過的節點（集合）
# parent 每次yield的父節點，有可能不存在
def preorder_traversal(root, seen=None, parent=None):
    """Generator function to yield the edges via a preorder traversal."""
    if seen is None: # 如果沒有開始遍歷，seen是空，初始化集合
        seen = set()
    yield (parent, root) # 記一次輸出，這個要在下面判斷之前
    if root in seen: # 要遍歷的根節點是否已經遍歷過，防止循環遍歷
        return
    seen.add(root) # 保存已遍歷的“根”節點
    for node in root: # 遍歷子節點
        for (parent, subnode) in preorder_traversal(node, seen, root):
            yield (parent, subnode)
    return

一開始不明白的地方是這樣

    yield (parent, root) # 記一次輸出，這個要在下面判斷之前
    if root in seen: # 要遍歷的根節點是否已經遍歷過，防止循環遍歷
        return

為什么不是先判斷呢。
看循環引用的情況。
前序輸出從root -> a -> b -> a這一路下來，有兩個a是正確的，
如果先判斷要遍歷的節點是否已經遍歷過的話，那么
b -> a就走不通了，所以應該允許，點到就記一次輸出，再來判斷是否能繼續往下走。
b -> a記一次輸出，接下來發現a已經遍歷過它的子節點了(a in seen)，才停止不往下遍歷。