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

yipeiwu_com5年前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=left
    self.right=right
  #setter and getter
  def get_val(self):
    return self.val
  def set_val(self,val):
    self.val=val
  def get_left(self):
    return self.left
  def set_left(self,left):
    self.left=left
  def get_right(self):
    return self.right
  def set_right(self,right):
    self.right=right
class Tree:
  def __init__(self,list):
    list=sorted(list)
    self.root=self.build_tree(list)
  #递归建立平衡二叉树
  def build_tree(self,list):
    l=0
    r=len(list)-1
    if(l>r):
      return None
    if(l==r):
      return Node(list[l])
    mid=(l+r)/2
    root=Node(list[mid])
    root.left=self.build_tree(list[:mid])
    root.right=self.build_tree(list[mid+1:])
    return root
  #前序遍历
  def preorder(self,root):
    if(root is None):
      return
    print root.val
    self.preorder(root.left)
    self.preorder(root.right)
  #后序遍历
  def postorder(self,root):
    if(root is None):
      return
    self.postorder(root.left)
    self.postorder(root.right)
    print root.val
  #中序遍历
  def inorder(self,root):
    if(root is None):
      return
    self.inorder(root.left)
    print root.val
    self.inorder(root.right)
  #层序遍历
  def levelorder(self,root):
    if root is None:
      return
    queue =deque([root])
    while(len(queue)>0):
      size=len(queue)
      for i in range(size):
        node =queue.popleft()
        print node.val
        if node.left is not None:
          queue.append(node.left)
        if node.right is not None:
          queue.append(node.right)
list=[1,-1,3,4,5]
tree=Tree(list)
print '中序遍历:'
tree.inorder(tree.root)
print '层序遍历:'
tree.levelorder(tree.root)
print '前序遍历:'
tree.preorder(tree.root)
print '后序遍历:'
tree.postorder(tree.root)

输出:

中序遍历
-1
1
3
4
5
层序遍历
3
-1
4
1
5
前序遍历
3
-1
1
4
5
后序遍历
1
-1
5
4
3

建立的二叉树如下图所示:

PS:作者的github: https://github.com/zhoudayang

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

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

相关文章

详解Python list 与 NumPy.ndarry 切片之间的对比

详解Python list 与 NumPy.ndarry 切片之间的区别 实例代码: # list 切片返回的是不原数据,对新数据的修改不会影响原数据 In [45]: list1...

Python操作MySQL数据库的方法

pymsql pymsql是Python中操作MySQL的模块,其使用方法和MySQLdb几乎相同。 下载安装 pip3 install pymysql 使用操作 1、执行SQL i...

Python断言assert的用法代码解析

在开发一个程序时候,与其让它运行时崩溃,不如在它出现错误条件时就崩溃(返回错误)。这时候断言assert 就显得非常有用。 python assert断言是声明布尔值必须为真的判定,如果...

Python实现Kmeans聚类算法

本节内容:本节内容是根据上学期所上的模式识别课程的作业整理而来,第一道题目是Kmeans聚类算法,数据集是Iris(鸢尾花的数据集),分类数k是3,数据维数是4。 关于聚类  ...

单利模式及python实现方式详解

单例模式 单例模式(Singleton Pattern)是一种常用的软件设计模式,该模式的主要目的是确保 某一个类只有一个实例存在 。当希望在整个系统中,某个类只能出现一个实例时,单例对...