Python实现二叉树的常见遍历操作总结【7种方法】

 更新时间:2019年03月06日 14:45:12   作者:wenkenza5368   我要评论
这篇文章主要介绍了Python实现二叉树的常见遍历操作,结合实例形式总结分析了二叉树的前序、中序、后序、层次遍历中的迭代与递归等7种操作方法,需要的朋友可以参考下

本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考,具体如下:

二叉树的定义:

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

二叉树的前序遍历

递归

def preorder(root,res=[]):
  if not root:
    return 
  res.append(root.val)
  preorder(root.left,res)
  preorder(root.right,res)
  return res

迭代

def preorder(root):
  res=[]
  if not root: 
    return []
  stack=[root]
  while stack:
    node=stack.pop()
    res.append(node.val)
    if node.right:
      stack.append(node.right)
    if node.left:
      stack.append(node,left)
  return res

二叉树的中序遍历

递归

def inorder(root,res=[]):
  if not root:
    return 
  inorder(root.left,res)
  res.append(root.val)
  inorder(root.right,res)
  return res

迭代

def inorder(root):
  stack=[]
  node=root
  res=[]
  while stack or node:
    while node:
      stack.append(node)
      node=node.left
    node=stack.pop()
    res.append(node.val)
    node=node.right
  return res

二叉树的后序遍历

递归

def laorder(root,res=[]):
  if not root:
    return 
  laorder(root.left,res)
  laorder(root.right,res)
  res.append(root.val)
  return res

迭代

def laorder(root):
  stack=[root]
  res=[]
  while stack:
    node=stack.pop()
    if node.left:
      stack.append(node.left)
    if node.right:
      stack.append(node.right)
    res.append(node.val)
  return res[::-1]

二叉树的层次遍历

迭代

def levelorder(root):
  queue=[root]
  res=[]
  while queue:
    node=queue.pop(0)
    if node.left: 
      queue.append(node.left)
    if node.right:
      queue.append(node.right)
    res.append(node.val)
  return res

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

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

相关文章

  • Django缓存系统实现过程解析

    Django缓存系统实现过程解析

    这篇文章主要介绍了Django缓存系统实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
    2019-08-08
  • 浅析Python基础-流程控制

    浅析Python基础-流程控制

    Python编程语言的作用非常强大,而且其应用方便的特点也对开发人员起到了非常大的作用。在这里我们就可以先从Python流程控制关键字的相关概念开始了解,从而初步掌握这一语言的特点
    2016-03-03
  • python使用PyGame播放Midi和Mp3文件的方法

    python使用PyGame播放Midi和Mp3文件的方法

    这篇文章主要介绍了python使用PyGame播放Midi和Mp3文件的方法,涉及Python操作多媒体文件的相关技巧,需要的朋友可以参考下
    2015-04-04
  • Django静态资源URL STATIC_ROOT的配置方法

    Django静态资源URL STATIC_ROOT的配置方法

    这篇文章主要介绍了Django静态资源URL STATIC_ROOT的配置方法,本文给出配置方法和两种使用方法,需要的朋友可以参考下
    2014-11-11
  • Python中for循环详解

    Python中for循环详解

    这篇文章主要介绍了Python中for循环,有需要的朋友可以参考一下
    2014-01-01
  • Python中typing模块与类型注解的使用方法

    Python中typing模块与类型注解的使用方法

    这篇文章主要给大家介绍了关于Python中typing模块与类型注解的使用方法,文中通过示例代码介绍的非常详细,对大家学习或者使用Python具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
    2019-08-08
  • python动态网页批量爬取

    python动态网页批量爬取

    这篇文章主要介绍了python动态网页批量爬取的方法,主要针对四六级成绩批量爬取,感兴趣的小伙伴们可以参考一下
    2016-02-02
  • Python实现的登录验证系统完整案例【基于搭建的MVC框架】

    Python实现的登录验证系统完整案例【基于搭建的MVC框架】

    这篇文章主要介绍了Python实现的登录验证系统,结合完整实例形式分析了Python基于搭建的MVC框架进行登录验证操作的相关实现与使用技巧,需要的朋友可以参考下
    2019-04-04
  • Python随机生成数模块random使用实例

    Python随机生成数模块random使用实例

    这篇文章主要介绍了Python随机生成数模块random使用实例,本文直接给出示例代码,需要的朋友可以参考下
    2015-04-04
  • 解决python 3 urllib 没有 urlencode 属性的问题

    解决python 3 urllib 没有 urlencode 属性的问题

    今天小编就为大家分享一篇解决python 3 urllib 没有 urlencode 属性的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-08-08

最新评论