欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-02 17:01:10
本文实例讲述了python实现的二叉树定义与遍历算法。分享给大家供大家参考,具体如下: 初学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

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

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

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

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

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