python实现树的深度优先遍历与广度优先遍历详解

本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考，具体如下：

广度优先(层次遍历)

从树的root开始，从上到下从左到右遍历整个树的节点

数和二叉树的区别就是，二叉树只有左右两个节点

广度优先 顺序：A - B - C - D - E - F - G - H - I

代码实现

def breadth_travel(self, root):
    """利用队列实现树的层次遍历"""
    if root == None:
      return
    queue = []
    queue.append(root)
    while queue:
      node = queue.pop(0)
      print node.elem,
      if node.lchild != None:
        queue.append(node.lchild)
      if node.rchild != None:
        queue.append(node.rchild)

深度优先

深度优先有三种算法：前序遍历，中序遍历，后序遍历

先序遍历 在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树

根节点->左子树->右子树

 #实现 1
 def preorder(self, root):
    """递归实现先序遍历"""
    if root == None:
      return
    print root.elem
    self.preorder(root.lchild)
    self.preorder(root.rchild)

 #实现 2
 def depth_tree(tree_node):
   if tree_node is not None:
     print (tree_node._data)
     if tree_node._left is noe None:
       return depth_tree(tree_node._left)
     if tree_node._right is not None:
       return depth_tree(tree_node._right)

中序遍历 在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树

左子树->根节点->右子树

def inorder(self, root):
   """递归实现中序遍历"""
   if root == None:
     return
   self.inorder(root.lchild)
   print root.elem
   self.inorder(root.rchild)

后序遍历 在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点

左子树->右子树->根节点

def postorder(self, root):
   """递归实现后续遍历"""
   if root == None:
     return
   self.postorder(root.lchild)
   self.postorder(root.rchild)
   print root.elem

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python操作列表常用方法实例小结【创建、遍历、统计、切片等】

    Python操作列表常用方法实例小结【创建、遍历、统计、切片等】

    本文实例讲述了Python操作列表常用方法.分享给大家供大家参考,具体如下: 使用for循环,遍历整个列表 依次从列表中取出元素,存放到names变量中,并拼接打印 names = ['杜子腾','杜小月','杜小星','杜小阳','杜小花'] for name in names: print("你好啊"+" "+name+" "+"我们交个朋友吧") 运行结果: 你好啊 杜子腾 我们交个朋友吧 你好啊 杜小月 我们交个朋友吧

  • Python列表原理与用法详解【创建、元素增加、删除、访问、计数、切片、遍历等】

    本文实例讲述了Python列表原理与用法.分享给大家供大家参考,具体如下: 列表的基本认识 列表简介 列表的创建 基本语法[]创建 list()创建 range()创建整数列表 推导式生成列表(简介一下,重点在 for 循环后讲) 列表元素的增加 append()方法 +运算符操作 extend()方法 insert()插入元素 乘法扩展 列表元素的删除 del 删除 pop()方法 remove()方法 列表元素访问和计数 通过索引直接访问元素 index()获得指定元素在列表中首次出现的索引

  • 使用Python代码实现Linux中的ls遍历目录命令的实例代码

    一.写在前面 前几天在微信上看到这样一篇文章,链接为:https://www.jb51.net/it/692145.html,在这篇文章中,有这样一段话,吸引了我的注意: 在 Linux 中 ls 是一个使用频率非常高的命令了,可选的参数也有很多, 算是一条不得不掌握的命令.Python 作为一门简单易学的语言,被很多人认为是不需要认真学的,或者只是随便调个库就行了,那可就真是小瞧 Python 了.那这次我就要试着用 Python 来实现一下 Linux 中的 ls 命令, 小小地证明下 Py

  • python爬虫之遍历单个域名

    即使你没听说过"维基百科六度分隔理论",也很可能听过"凯文 • 贝肯 (Kevin Bacon)的六度分隔值游戏".在这两个游戏中,目标都是把两 个不相干的主题(在前一种情况中是相互链接的维基百科词条,而在后 一种情况中是出现在同一部电影中的演员)用一个链条(至多包含 6 个 主题,包括原来的两个主题)连接起来. 比如,埃里克 • 艾德尔和布兰登 • 弗雷泽都出现在电影<骑警杜德雷> 里,布兰登 • 弗雷泽又和凯文 • 贝肯都出现在电影<我呼吸的空

  • Python字典常见操作实例小结【定义、添加、删除、遍历】

    本文实例总结了Python字典常见操作.分享给大家供大家参考,具体如下: 简单的字典: 字典就是键值对key-value组合. #字典 键值对组合 alien_0 ={'color':'green','number':5} print(alien_0['color']) print(alien_0['number']) 运行结果: green 5 添加键值对 alien_0 ={'color':'green','number':5} alien_0['first_name'] = 'mo' al

  • python实现树的深度优先遍历与广度优先遍历详解

    python实现树的深度优先遍历与广度优先遍历详解

    本文实例讲述了python实现树的深度优先遍历与广度优先遍历.分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个节点 广度优先 顺序:A - B - C - D - E - F - G - H - I 代码实现 def breadth_travel(self, root): """利用队列实现树的层次遍历""" if root == None: r

  • JavaScript树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了JavaScript树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1.深度优先遍历的递归写法 function deepTraversal(node) { var nodes = []; if (node != null) { nodes.push(node); var children = node.children; for (var i = 0; i < children.length; i++) deepTraversal(children[i]);

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • 对python 树状嵌套结构的实现思路详解

    原始数据 原始数据大致是这样子的: 每条数据中的四个数据分别是 当前节点名称,节点描述(指代一些需要的节点属性),源节点(即最顶层节点),父节点(当前节点上一层节点). datas = [ ["root", "根节点", "root", None], ["node1", "一级节点1", "root", "root"], ["node2", &qu

  • 利用Python代码实现数据可视化的5种方法详解

    利用Python代码实现数据可视化的5种方法详解

    前言 数据科学家并不逊色于艺术家.他们用数据可视化的方式绘画,试图展现数据内隐藏的模式或表达对数据的见解.更有趣的是,一旦接触到任何可视化的内容.数据时,人类会有更强烈的知觉.认知和交流. 数据可视化是数据科学家工作中的重要组成部分.在项目的早期阶段,你通常会进行探索性数据分析(Exploratory Data Analysis,EDA)以获取对数据的一些理解.创建可视化方法确实有助于使事情变得更加清晰易懂,特别是对于大型.高维数据集.在项目结束时,以清晰.简洁和引人注目的方式展现最终结果是非常

  • 对python中的控制条件、循环和跳出详解

    对python中的控制条件.循环和跳出详解 代码缩进(代码块): python用缩进表示代码块,没有其他语言的大括号 缩进是强制检查,整个代码缩进必须一致,否则无法运行 用2.4个空格或者tab缩进 ide自动保证缩进一致 If.elif和else的条件分支: if if...else if...elif..else 没有switch.case语法 空的列表.元祖.字符串.0都被评估为False None被评估为False 控制条件后面必须加":" a=100 if a > 80

  • Python数据类型之列表和元组的方法实例详解

    引言 我们前面的文章介绍了数字和字符串,比如我计算今天一天的开销花了多少钱我可以用数字来表示,如果是整形用 int ,如果是小数用 float ,如果你想记录某件东西花了多少钱,应该使用 str 字符串型,如果你想记录表示所有开销的物品名称,你应该用什么表示呢? 可能有人会想到我可以用一个较长的字符串表示,把所有开销物品名称写进去,但是问题来了,如果你发现你记录错误了,想删除掉某件物品的名称,那你是不是要在这个长字符串中去查找到,然后删除,这样虽然可行,那是不是比较麻烦呢. 这种情况下,你是不是

  • Python中zip()函数的解释和可视化(实例详解)

    zip()的作用 先看一下语法: zip(iter1 [,iter2 [...]]) -> zip object Python的内置help()模块提供了一个简短但又有些令人困惑的解释: 返回一个元组迭代器,其中第i个元组包含每个参数序列或可迭代对象中的第i个元素.当最短的可迭代输入耗尽时,迭代器将停止.使用单个可迭代参数,它将返回1元组的迭代器.没有参数,它将返回一个空的迭代器. 与往常一样,当您精通更一般的计算机科学和Python概念时,此模块非常有用.但是,对于初学者来说,这段话只会引发更

  • python爬虫爬取监控教务系统的思路详解

    这几天考了大大小小几门课,教务系统又没有成绩通知功能,为了急切想知道自己挂了多少门,于是我写下这个脚本. 设计思路: 设计思路很简单,首先对已有的成绩进行处理,变为list集合,然后定时爬取教务系统查成绩的页面,对爬取的成绩也处理成list集合,如果newList的长度增加了,就找出增加的部分,并通过邮件通知我. 脚本运行效果: 服务器: 发送邮件通知: 代码如下: import datetime import time from email.header import Header impor

  • Python日志打印里logging.getLogger源码分析详解

    实践环境 WIN 10 Python 3.6.5 函数说明 logging.getLogger(name=None) getLogger函数位于logging/__init__.py脚本 源码分析 _loggerClass = Logger # ...略 root = RootLogger(WARNING) Logger.root = root Logger.manager = Manager(Logger.root) # ...略 def getLogger(name=None): "&quo

随机推荐