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

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

相关文章

Python中删除文件的程序代码

Python是一种面向对象的解释性的计算机程序设计语言,也是一种功能强大而完善的通用型语言,已经具有十多年的发展历史,成熟且稳定。Python 具有脚本语言中最丰富和强大的类库,足以支持...

深入了解和应用Python 装饰器 @decorator

深入了解和应用Python 装饰器 @decorator

Python的装饰器(decorator)是一个很棒的机制,也是熟练运用Python的必杀技之一。装饰器,顾名思义,就是用来装饰的,它装饰的是一个函数,保持被装饰函数的原有功能,再装饰...

Python中字符串的常见操作技巧总结

本文实例总结了Python中字符串的常见操作技巧。分享给大家供大家参考,具体如下: 反转一个字符串 >>> S = 'abcdefghijklmnop' >&...

Python实现定期检查源目录与备份目录的差异并进行备份功能示例

本文实例讲述了Python实现定期检查源目录与备份目录的差异并进行备份功能。分享给大家供大家参考,具体如下: 在项目中,经常要更新文件,在更新之前首先要备份源文件,所以就用到了这个脚本(...

利用python和百度地图API实现数据地图标注的方法

利用python和百度地图API实现数据地图标注的方法

如题,先上效果图: 主要分为两大步骤 使用python语句,通过百度地图API,对已知的地名抓取经纬度 使用百度地图API官网的html例程,修改数据部分,实现呈现效果 一、使用pyt...