这里有新鲜出炉的Python多线程编程,程序狗速度看过来!
Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。
这篇文章主要介绍了python实现的二叉树定义与遍历算法,结合具体实例形式分析了基于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程序设计有所帮助。
来源: http://www.phperz.com/article/17/1028/351304.html