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

Python  /  管理员 发布于 7年前   158

本文实例讲述了python实现的二叉树定义与遍历算法。分享给大家供大家参考，具体如下：

初学python，需要实现一个决策树，首先实践一下利用python实现一个二叉树数据结构。建树的时候做了处理，保证建立的二叉树是平衡二叉树。

# -*- coding: utf-8 -*-from collections import dequeclass 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=rightclass 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)

输出：

中序遍历-11345层序遍历3-1415前序遍历3-1145后序遍历1-1543

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

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

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

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