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程序设计有所帮助。

时间: 2018-12-23

Python利用前序和中序遍历结果重建二叉树的方法

本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''

Python二叉树定义与遍历方法实例分析

本文实例讲述了Python二叉树定义与遍历方法.分享给大家供大家参考,具体如下: 二叉树基本概述: 二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质: 1. 二叉树的每个结点不存在度大于2的结点 2. 二叉树的第i层至多有2^{i-1}个结点 3. 深度为k的二叉树至多有2^k - 1个结点 4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0 Python代码: #codin

python先序遍历二叉树问题

问题 如何遍历一个二叉树 遍历二叉树就是访问二叉树的每一个节点 二叉树父结点下先左访问,先序遍历(根左右) 例如:遍历以下的二叉树 遍历结果:ABDECF Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): ''' 二叉树类 ''' def __init__ (self, data, left = None, right

Python定义二叉树及4种遍历方法实例详解

本文实例讲述了Python定义二叉树及4种遍历方法.分享给大家供大家参考,具体如下: Python & BinaryTree 1. BinaryTree (二叉树) 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和右子树的二叉树组成. 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒. 二叉树的第i层至多有2^{i-1}个结点 深度为k的二叉树至多有2^k-1个结点: 对任何一棵二叉

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

python数据结构之二叉树的遍历实例

遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

python实现的二叉树定义与遍历算法实例

本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树的建立 使用类的形式定义二叉树,可读性更好 class BinaryTree: def __init__(self, root): self.key = root self.left_child = None self.right_child = None def insert_left(self, new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTr

Python编程实现二叉树及七种遍历方法详解

本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl

Python数据结构与算法之二叉树结构定义与遍历方法详解

本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

java中关于Map的三种遍历方法详解

map的三种遍历方法!集合的一个很重要的操作---遍历,学习了三种遍历方法,三种方法各有优缺点~~ 复制代码 代码如下: /* * To change this template, choose Tools | Templates * and open the template in the editor. */package cn.tsp2c.liubao;import java.util.Collection;import java.util.HashMap;import java.util

C 语言二叉树几种遍历方法详解及实例

二叉树的一些概念 二叉树就是每个结点最多有两个子树的树形存储结构.先上图,方便后面分析. 1 满二叉树和完全二叉树 上图就是典型的二叉树,其中左边的图还叫做满二叉树,右边是完全二叉树.然后我们可以得出结论,满二叉树一定是完全二叉树,但是反过来就不一定.满二叉树的定义是除了叶子结点,其它结点左右孩子都有,深度为k的满二叉树,结点数就是2的k次方减1.完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应. 2 树的深度 树的最大层次就是深度,比如上图,深度是4.很容易得出,深度为k的树,

C#编程高并发的几种处理方法详解

并发(英文Concurrency),其实是一个很泛的概念,字面意思就是"同时做多件事",不过方式有所不同.在.NET的世界里面,处理高并发大致有以下几种方法: 1.异步编程 异步编程就是使用future模式(又称promise)或者回调机制来实现(Non-blocking on waiting).如果使用回调或事件来实现(容易callback hell),不仅编写这样的代码不直观,很快就容易把代码搞得一团糟. 不过在.NET 4.5 及以上框架中引入的async/await关键字(在.

Python之关于类变量的两种赋值区别详解

我就废话不多说了,还是直接看代码吧! # -*- coding:utf-8 -*- #面试题,写一个方法,将一行字符串中所有的单词数量统计出来 class Person(object): TAG = "hello" p1 = Person() p2 = Person() print p1.TAG #第一种赋值方式 print p2.TAG print Person.TAG #第二种赋值方式 p1.TAG = "damn it" print p1.TAG print

JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】

本文实例讲述了JavaScript实现的DOM树遍历方法.分享给大家供大家参考,具体如下: 二叉 DOM 树的遍历 function Tree() { var Node = function(key){ this.key = key; this.left = null; this.right = null; } root =null; } 前序遍历 首先访问根结点,然后遍历左子树,最后遍历右子树 Tree.prototype.preOrderTraverse = function(callbac

基于Python的Post请求数据爬取的方法详解

为什么做这个 和同学聊天,他想爬取一个网站的post请求 观察 该网站的post请求参数有两种类型:(1)参数体放在了query中,即url拼接参数(2)body中要加入一个空的json对象,关于为什么要加入空的json对象,猜测原因为反爬虫.既有query参数又有空对象体的body参数是一件脑洞很大的事情. 一开始先在apizza网站 上了做了相关实验才发现上面这个规律的,并发现该网站的请求参数要为raw形式,要是直接写代码找规律不是一件容易的事情. 源码 import requests im

对python抓取需要登录网站数据的方法详解

scrapy.FormRequest login.py class LoginSpider(scrapy.Spider): name = 'login_spider' start_urls = ['http://www.login.com'] def parse(self, response): return [ scrapy.FormRequest.from_response( response, # username和password要根据实际页面的表单的name字段进行修改 formdat