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

yipeiwu_com5年前Python基础

本文实例讲述了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程序设计有所帮助。

相关文章

python 把文件中的每一行以数组的元素放入数组中的方法

有时候需要把文件中的数据放入到数组中,这里提供了一种方法,可以根据文件结尾的标记进行数据拆分,然后再把拆分的文件放入数组中 # -*-coding: utf-8 -*- f = op...

和孩子一起学习python之变量命名规则

变量命名规则 下面是关于变量名(也称为标识符)的一些规则 必须以一个字母或一个下划线字符开头。后面可以使用一个字母、数字或下划线字符的序列,长度不限。 字母可以是大写或小写,大小写...

Python操作SQLite简明教程

一、SQLite简介 SQLite是一个包含在C库中的轻量级数据库。它并不需要独立的维护进程,并且允许使用非标准变体(nonstandard variant)的SQL查询语句来访问数据库...

python遍历类中所有成员的方法

本文实例讲述了python遍历类中所有成员的方法。分享给大家供大家参考。具体分析如下: 这段代码自定义了一个类,类包含了两个成员title和url,在类的内部定义了一个函数list_al...

把JSON数据格式转换为Python的类对象方法详解(两种方法)

把JSON数据格式转换为Python的类对象方法详解(两种方法)

JOSN字符串转换为自定义类实例对象 有时候我们有这种需求就是把一个JSON字符串转换为一个具体的Python类的实例,比如你接收到这样一个JSON字符串如下: {"Name": "...