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

本文实例讲述了Python二叉树定义与遍历方法。分享给大家供大家参考,具体如下:

二叉树基本概述:

二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质:

1. 二叉树的每个结点不存在度大于2的结点
2. 二叉树的第i层至多有2^{i-1}个结点
3. 深度为k的二叉树至多有2^k - 1个结点
4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0

Python代码:

#coding:utf-8
'BiTree'
class Node(object):
  'Node Defination'
  def __init__(self,item):
    self.item = item
    self.left = None
    self.right = None
class Tree(object):
  'Bitree Defination'
  def __init__(self):
    self.root = None
  def add(self,item):
    node = Node(item)
    if self.root is None:
      self.root = node
    else:
      q = [self.root]
      while True:
        pop_node = q.pop(0)
        if pop_node.left is None:
          pop_node.left = node
          return
        elif pop_node.right is None:
          pop_node.right = node
          return
        else:
          q.append(pop_node.left)
          q.append(pop_node.right)
  def traverse(self):#层次遍历
    if self.root is None:
      return None
    q = [self.root]
    res = [self.root.item]
    while q != []:
      pop_node = q.pop(0)
      if pop_node.left is not None:
        q.append(pop_node.left)
        res.append(pop_node.left.item)
      if pop_node.right is not None:
        q.append(pop_node.right)
        res.append(pop_node.right.item)
    return res
  def preorder(self,root): #先序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.preorder(root.left)
    right_item = self.preorder(root.right)
    return result + left_item + right_item
  def inorder(self,root): #中序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.inorder(root.left)
    right_item = self.inorder(root.right)
    return left_item + result + right_item
  def postorder(self,root): #后序遍历
    if root is None:
      return []
    result = [root.item]
    left_item = self.postorder(root.left)
    right_item = self.postorder(root.right)
    return left_item + right_item + result
if __name__=='__main__':
  t = Tree()
  for i in range(10):
    t.add(i)
  print "层序遍历:",t.traverse()
  print "先序遍历:",t.preorder(t.root)
  print "中序遍历:",t.inorder(t.root)
  print "后序遍历:",t.postorder(t.root)

输出结果:

层序遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

这里对于

if __name__=='__main__':
“Make a script both importable and executable”

意思就是说让你写的脚本模块既可以导入到别的模块中用,另外该模块自己也可执行。

这里通过一个示例进行解释:

#test.py
def func():
 print "we are in %s"%__name__
if __name__ == '__main__':
 func()

输出结果:

we are in __main__

说明if语句中的内容被执行了,调用了 func()函数,现在在另一个模块中调用func函数

#testtest
from test import func
func()

输出结果:

we are in moudle

也就是说 if 条件中的内容没有执行。

总结:

如果直接执行某个*.py文件,该文件中 if __name__ == '__main__'是True,相当于调式本模块的代码;如果是从另一个模块(testtest.py)通过import导入该文件的时候,这时__name__就是这个模块的名字(test)而不是__main__,总之在调式代码的时候加上 if __name__ == '__main__'中加入调试代码,可以让步模块调用的时候不执行调式代码,如果想排查本模块代码的问题时,直接进行调试执行

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

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

(0)

相关推荐

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

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

  • 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定义二叉树及4种遍历方法实例详解

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

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

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

  • 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数据结构之二叉树的遍历实例

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

  • 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二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

    本文实例讲述了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)的元素及两个互不相交的.分别被称为左子树和

  • 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二叉树定义与遍历方法实例分析

    本文实例讲述了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存取XML的常见方法实例分析

    本文实例讲述了Python存取XML的常见方法.分享给大家供大家参考,具体如下: 目前而言,Python 3.2存取XML有以下四种方法: 1.Expat 2.DOM 3.SAX 4.ElementTree 以以下xml作为讨论依据 <?xml version="1.0" encoding="utf-8"?> <Schools> <School Name="XiDian"> <Class Id="

  • python实现数值积分的Simpson方法实例分析

    本文实例讲述了python实现数值积分的Simpson方法.分享给大家供大家参考.具体如下: #coding = utf-8 #simpson 法计算积分,数值积分,效果非常理想 from math import * def func(x): """ 定义被积分函数 """ return x*sin(x) def Get_N(a,b,width): # width为步长 N=int((b-a)/width + 1) if N%2 == 0: N=

  • python中base64加密解密方法实例分析

    本文实例讲述了python中base64加密解密方法.分享给大家供大家参考.具体分析如下: 一.base64 Base64是一种基于64个可打印字符来表示二进制数据的表示方法.由于2的6次方等于64,所以每6个比特为一个单元,对应某个可打印字符.三个字节有24个比特,对应于4个Base64单元,即3个字节需要用4个可打印字符来表示.它可用来作为电子邮件的传输编码.在Base64中的可打印字符包括字母A-Z.a-z.数字0-9 ,这样共有62个字符,此外两个可打印符号在不同的系统中而不同.编码后的

  • Python对列表排序的方法实例分析

    本文实例讲述了Python对列表排序的方法.分享给大家供大家参考.具体分析如下: 1.sort()函数 sort()函数使用固定的排序算法对列表排序.sort()函数对列表排序时改变了原来的列表,从而让其中的元素能按一定的顺序排列,而不是简单的返回一个已排序的列表副本. 注意sort()函数改变原来的列表,函数返回值是空值即None.因此,如果需要一个已排好序的列表副本,同时又要保留原有列表不变的时候,就不能直接简单的使用sort()函数.为了实现上述功能使用sort()的方法是:先获取列表X的

  • Python生成器定义与简单用法实例分析

    本文实例讲述了Python生成器定义与简单用法.分享给大家供大家参考,具体如下: 一.什么是生成器 在Python中,由于受到内存的限制,列表容量肯定是有限的.例如我们创建一个包含一亿个元素的列表,Python首先会在内存中开辟足够的空间来存储这个包含一亿个元素的列表,然后才允许用户去使用这个列表,这就可能会导致以下问题: 1.内存中没有足够的内存空间开存储这个列表,从而导致列表无法创建 2.即使列表成功创建,然而仍会消耗很长的时间,导致程序效率低下 3.若用户只想访问列表前面的几个元素,则后面

  • json的结构与遍历方法实例分析

    本文实例讲述了json的结构与遍历方法.分享给大家供大家参考,具体如下: 第一种json结构: var jsongood = {"goods":[{"parentId":"null","productId":1,"name":"商品","amount":"null"},{"parentId":1,"productId&

  • Python爬虫DNS解析缓存方法实例分析

    本文实例讲述了Python爬虫DNS解析缓存方法.分享给大家供大家参考,具体如下: 前言: 这是Python爬虫中DNS解析缓存模块中的核心代码,是去年的代码了,现在放出来 有兴趣的可以看一下. 一般一个域名的DNS解析时间在10~60毫秒之间,这看起来是微不足道,但是对于大型一点的爬虫而言这就不容忽视了.例如我们要爬新浪微博,同个域名下的请求有1千万(这已经不算多的了),那么耗时在10~60万秒之间,一天才86400秒.也就是说单DNS解析这一项就用了好几天时间,此时加上DNS解析缓存,效果就

  • Python动态导入模块的方法实例分析

    本文实例讲述了Python动态导入模块的方法.分享给大家供大家参考,具体如下: 一.正常导入模块 正常模块导入方式: import module(模块路径) 同时导入多个模块: import os,sys,socket 二.动态导入模块 动态导入模块允许我们通过字符串形式来导入模块 2.1 __import__函数,接受一个字符串参数 import os, sys my_sys = __import__('sys') my_os = __import__('os') print(sys.vers

随机推荐