Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

yipeiwu_com6年前Python基础

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

# coding:utf-8
"""
@ encoding: utf-8
@ author: lixiang
@ email: lixiang_cn@foxmail.com
@ python_version: 2
@ time: 2018/4/11 0:09
@ more_info:
二叉树是有限个元素的集合,该集合或者为空、或者有一个称为根节点(root)的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
1 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
2 二叉树的第i层至多有2^{i-1}个结点
3 深度为k的二叉树至多有2^k-1个结点;
4 对任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1
5 度是二叉树分支树,对于二叉树而言有0,1,2三种取值
不管是前中后序遍历,都是在当前规则下,无路可走时,输出根结点。
"""
class TreeNode(object):
  def __init__(self, x, left=None, right=None):
    self.val = x
    self.left = left
    self.right = right
def pre_traverse(root):
  """
  根左右
  :param root:
  :return:
  """
  if not root:
    return
  print root.val,
  pre_traverse(root.left)
  pre_traverse(root.right)
def mid_travese(root):
  """
  左根右
  :param root:
  :return:
  """
  if not root:
    return
  mid_travese(root.left)
  print root.val,
  mid_travese(root.right)
def after_travese(root):
  """
  左右根
  :param root:
  :return:
  """
  if not root:
    return
  after_travese(root.left)
  after_travese(root.right)
  print root.val,
def level_travese(root):
  if not root:
    return
  queue = []
  queue.append(root)
  while queue:
    cur = queue.pop(0)
    print cur.val,
    if cur.left:
      queue.append(cur.left)
    if cur.right:
      queue.append(cur.right)
def depth(root):
  if not root:
    return 0
  left = depth(root.left)
  right = depth(root.right)
  return max(left, right) + 1
if __name__ == '__main__':
  """
  tree是一个表示树根节点的对象
  前序遍历 1 2 4 5 8 9 11 3 6 7 10
  中序遍历 4 2 8 5 11 9 1 6 3 10 7
  后序遍历 4 8 11 9 5 2 6 10 7 3 1
  层序遍历 1 2 3 4 5 6 7 8 9 10 11
  深度 5
  """
  tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8), TreeNode(9, left=TreeNode(11)))), TreeNode(3, TreeNode(6), TreeNode(7, left=TreeNode(10))))
  print("\n前序遍历")
  pre_traverse(tree)
  print("\n中序遍历")
  mid_travese(tree)
  print("\n后序遍历")
  after_travese(tree)
  print("\n层序遍历")
  level_travese(tree)
  print("\n深度")
  print(depth(tree))

运行结果:

前序遍历
1 2 4 5 8 9 11 3 6 7 10
中序遍历
4 2 8 5 11 9 1 6 3 10 7
后序遍历
4 8 11 9 5 2 6 10 7 3 1
层序遍历
1 2 3 4 5 6 7 8 9 10 11
深度
5

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

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

相关文章

关于ZeroMQ 三种模式python3实现方式

关于ZeroMQ 三种模式python3实现方式

ZeroMQ是一个消息队列网络库,实现网络常用技术封装。在C/S中实现了三种模式,这段时间用python简单实现了一下,感觉python虽然灵活。但是数据处理不如C++自由灵活。 Req...

详解python中executemany和序列的使用方法

详解python中executemany和序列的使用方法 一 代码 import sqlite3 persons=[ ("Jim","Green"), ("Hu","...

在Python中操作字典之update()方法的使用

 update()方法添加键 - 值对到字典dict2。此函数不返回任何值。 语法 以下是update()方法的语法: dict.update(dict2) 参数...

python将字符串转变成dict格式的实现

python将字符串转变成dict格式的实现

字符串的内容是字典,需将字符串转变成字典格式 s1 = '{"lid":2,"date":"20190211","type":"1,2","page":1}' # dict的key和...

pytorch三层全连接层实现手写字母识别方式

pytorch三层全连接层实现手写字母识别方式

先用最简单的三层全连接神经网络,然后添加激活层查看实验结果,最后加上批标准化验证是否有效 首先根据已有的模板定义网络结构SimpleNet,命名为net.py import torc...