前序遍历树

代码来自: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),才停止不往下遍历。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用left join查找用户的所有同事

    为了找出某个用户所在组织(部门)的所有员工,即该用户的所有同事包括他自己,常见的做法是通过用户找到他所在的组织(部门),然后再通过部门找到所有的员工。而我在实践...

    用户3579639
  • 使用commons-pool管理FTP连接

    在封装一个FTP工具类文章,已经完成一版对FTP连接的管理,设计了模板方法,为工具类上传和下载文件方法的提供获取对象和释放对象支持。

    用户3579639
  • Sizzle.selectors.match/leftMatch

    对象Sizzle.selectors.match/leftMatch中存放了表达式类型和正则的映射,正则用于确定块表达式的类型,并解析其中的参数。

    用户3579639
  • Golang Leetcode 687. Longest Univalue Path.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Linux之安装Tomcat8 原

        修改List-5的server.xml,将port的值修改为其它值就可以了,默认值是8080

    克虏伯
  • Linux 系统中查找正在运行的进程的完整命令、当前工作目录等信息的方法

    在某些系统故障的排查过程中,需要找出某个应用程序的工作目录、完整命令行等信息。通常会通过ps及top等命令来查看进程信息,但往往只能查到相对路径、部分命令行等。...

    耕耘实录
  • LeetCode 二叉树 题目分类汇总

    简书的 markdown 都不支持 [TOC] 语法……我就不贴目录了。下面按照类别,列出了29道关于二叉树的题目。认真看会发现,其实题目核心思想都是DFS(如...

    Yano_nankai
  • Linux / MacOS 修改 ls 显示年月日的时间格式

    本文参考转自米扑博客:Linux / MacOS 修改 ls 显示年月日的时间格式

    阳光岛主
  • python中os. popen sy

    python调用Shell脚本或者是调用系统命令,有两种方法: os.system(cmd)或os.popen(cmd),前者返回值是脚本的退出状态码,正确会返...

    py3study
  • 快速搭建 Git 服务器[Linux版]

    找到server.httpBindInterface,设定服务器的IP地址。这里就设定你的服务器IP。

    一觉睡到小时候

扫码关注云+社区

领取腾讯云代金券