`
ilicis
  • 浏览: 13456 次
  • 性别: Icon_minigender_1
  • 来自: 上海
最近访客 更多访客>>
社区版块
存档分类
最新评论

平衡二叉树

Python 
阅读更多 

#!/usr/bin/env python
#coding=utf-8
import sys


#-------------------------------------------------------------------------------
#--------------------------- class BinaryTree define #---------------------------
#-------------------------------------------------------------------------------
class BTree(object):
   """
   base binary tree class
   three traverse function and get height function
   """
   def __init__(self,v,l,r,p):
       self.value = v
       self.lchild = l
       self.rchild = r
       self.parent = p
       self.bf = 0

   def show(self):
       """
       print the BinaryTree
       """
       print self.value
   
   def PreTrave(self):
       """
       previous order traverse the binary tree
       """
       if self.value is not None:
           self.show()
           if self.lchild is not None:
               self.lchild.PreTrave()
           if self.rchild is not None:
               self.rchild.PreTrave()
           
   def MidTrave(self):
       """
       Middle order traverse the binary tree
       """
       if self.value is not None:
           if self.lchild is not None:
               self.lchild.MidTrave()
           self.show()
           if self.rchild is not None:
               self.rchild.MidTrave()

   def PosTrave(self):
       """
       Post order traverse the binary tree
       """     
       if self.value is not None:
           if self.lchild is not None:
               self.lchild.PosTrave()
           if self.rchild is not None:
               self.rchild.PosTrave()
           self.show()
       
   def GetHeight(self):
       """
       get the height of the binarytree
       """
       if self.lchild is not None:
           hl = self.lchild.GetHeight()
       else:
           hl = 0
       if self.rchild is not None:
           hr = self.rchild.GetHeight()
       else:
           hr = 0
       return ((hl > hr) and hl or hr) + 1
       # return the larger height of child plus one

           


#-------------------------------------------------------------------------------
#---------------------------- Binary Search Tree #-------------------------------
#-------------------------------------------------------------------------------
class BSTree(BTree):
   """
   binary search tree , could add , delete but not balanced
   derived from class BTree(base binary tree)
   """
   def Find(self,key):
       global ptr
       global current
       ptr = self
       while ptr:
           if ptr.value == key:
               break
           if ptr.value < key:
               current = ptr
               ptr = ptr.rchild
           else:
               current = ptr
               ptr = ptr.lchild
       return ptr
   

   def Insert(self,key):
       global ptr
       global current
       find = self.Find(key)
       if find:
           return False
       global mode
       if mode == 2:
           ptr = BSTree(key,None,None,current)
       if mode == 1:
           ptr = AVLTree(key,None,None,current)
       if current.value > key:
           current.lchild = ptr
           ptr.parent = current
       else:
           current.rchild = ptr
           ptr.parent = current
       return True


   def RmvNode(self,key):
       if self.value == key:
           root = None
           self = None
           return False
       return self.__RmvNode(self.Find(key))


   def __RmvNode(self,ptr):
       global current
       if self.lchild is None or self.rchild is None:
           if self == ptr:
               self = (self.lchild is not None) and self.lchild or self.rchild
               current = self
               current.parent = None
               self.parent = None
               return True
       if ptr is None:
           return False
       tmp = ptr
       if ptr.lchild is None or ptr.rchild is None:
           if ptr.parent is None:
               root = ptr.lchild is None and ptr.rchild or ptr.lchild
               return True
           if ptr.lchild is None:
               if ptr.parent.lchild == ptr:
                   ptr.parent.lchild = ptr.rchild
               else:
                   ptr.parent.rchild = ptr.rchild
               ptr = ptr.rchild
           else:
               if ptr.parent.lchild == ptr:
                   ptr.parent.lchild = ptr.lchild
               else:
                   ptr.parent.rchild = ptr.lchild
               ptr = ptr.lchild
               if ptr:
                   ptr.parent = current
           return True
       if ptr.bf < 0:
           ptr = ptr.rchild
           while ptr.lchild:
               ptr = ptr.lchild
       else:
           ptr = ptr.lchild
           while ptr.rchild:
               ptr = ptr.rchild
       tmp.value = ptr.value
       current = ptr.parent
       if current.lchild == ptr:
           current.lchild = None
       else:
           current.rchild = None
       return True
       

#-------------------------------------------------------------------------------
#---------------------------------- AVL Tree #-----------------------------------
#-------------------------------------------------------------------------------
class AVLTree(BSTree):
   """
   AVL tree derived from BSTree(binary search tree)
   balanced dynamicly when data added and deleted
   """
   def AVLInsert(self,key):
       if self.Insert(key) == False:
           return False
       global ptr
       global current
       ptr = key
       while current is not None:
           cp = current.parent
           croot = (cp is not None) and ((cp.lchild == current) and (cp.lchild) or (cp.rchild)) or (root) 
           current.bf += (current.value > ptr) and 1 or -1
           if current.bf == -2:
               croot = croot.L_Balance()
           elif current.bf == 2:
               croot = croot.R_Balance()
           if current.bf == 0:
               break
           ptr = current.value
           current = current.parent
       while self.parent:
           self = self.parent
       return True
   
   
   def Remove(self,key):
       global current
       global rmvresult
       if self.RmvNode(key) == False:
           print "the tree is empty or no such node"
           return False
       while current:
           hl = (current.lchild) and current.lchild.GetHeight() or 0
           hr = (current.rchild) and current.rchild.GetHeight() or 0
           current.bf = hl - hr
           if current.bf == -2:
               current = current.L_Balance()
           elif current.bf == 2:
               current = current.R_Balance()
           if current.parent is None:
               break
           ptr = current
           current = current.parent
       self = current
       rmvresult = self
       return True


   def L_Balance(self):
       global current
       if (isinstance(self.rchild,AVLTree)) and (self.rchild.bf) == 1:
           self.rchild = (self.rchild).R_Rotate()
       self = self.L_Rotate()
       current = self
       return self

   def R_Balance(self):
       global current
       if (isinstance(self.lchild,AVLTree))and(self.lchild.bf) == -1:
           self.lchild = (self.lchild).L_Rotate()
       self = self.R_Rotate() 
       current = self
       return self


   def L_Rotate(self):
       tmp = self.rchild
       tmp.parent = (self.parent is not None) and (self.parent) or None
       if self.parent and self.parent.lchild == self:
           self.parent.lchild = tmp
       if self.parent and self.parent.rchild == self:
           self.parent.rchild = tmp
       self.parent = tmp
       self.rchild = (tmp.lchild is not None) and (tmp.lchild) or None
       if tmp.lchild:
           tmp.lchild.parent = self
       tmp.lchild = self
       self.bf += 1
       self.bf -= (tmp.bf < 0) and tmp.bf or 0
       tmp.bf += 1
       tmp.bf += (self.bf > 0) and self.bf or 0
       return tmp
  
  
   def R_Rotate(self):
       tmp = self.lchild
       tmp.parent = (self.parent is not None) and (self.parent) or None
       if self.parent and self.parent.lchild == self:
           self.parent.lchild = tmp
       if self.parent and self.parent.rchild == self:
           self.parent.rchild = tmp
       self.parent = tmp
       self.lchild = (tmp.rchild is not None) and tmp.rchild or None
       if tmp.rchild:
           tmp.rchild.parent = self
       tmp.rchild = self
       self.bf -= 1
       self.bf -= (tmp.bf > 0) and tmp.bf or 0
       tmp.bf -= 1
       tmp.bf += (self.bf < 0) and self.bf or 0
       return tmp
       


#-------------------------------------------------------------------------------
#------------------------------------ test #-------------------------------------
#-------------------------------------------------------------------------------
if __name__ == '__main__':
  print "1:avl tree , 2:binary search tree"
  while 1:
       try:
           t = raw_input()
           if int(t) == 1:
               mode = 1
               break
           if int(t) == 2:
               mode = 2
               break
       except ValueError:
           print "please choose 1 or 2"
  print "insert a number"
  t = raw_input()
  while t:
       try:

           if mode == 1:

               root = AVLTree((int(t)),None,None,None)
               break

           if mode == 2:

               root = BSTree((int(t)),None,None,None)
               break
       except ValueError:
           print "only int value acceptable"
  #1:avl tree , 2: bs tree
  while 1:
       try:
           print "insert a number"
           t = raw_input()
           if t == 'quit':
               break
           if mode == 1:
               if root.AVLInsert(int(t)) == False:
                   print "already exists"
               else:
                   while root.parent:
                       root = root.parent
                   print "now the avl tree:"
                   root.MidTrave()
           if mode == 2:
               if root.Insert(int(t)) == False:
                   print "already exists"
               else:
                   while root.parent:
                       root = root.parent
                   print "now the binary search tree:"
                   root.MidTrave()
       except ValueError:
           print "only int value acceptable"
  print "mid"
  root.MidTrave()
  print "now test delete function"
  while 1:
       print "which number you want to delete"
       t = raw_input()
       if t == 'quit':
           break
           try:
               if mode == 1:
                   if root.Remove(int(t)) == False:
                       print "no such node"
                   else:
                       root = rmvresult
               if mode == 2 and root.RmvNode(int(t)) == False:
                   print "no such node"
               print "after delete:"
               root.MidTrave()
           except ValueError:
           print "only int value acceptable"



来公司写的一个东西，当时是为了学习python
没想到还可以现在用来交作业。。。
说不定将来会用上
分享到：
| 两种抽象方式
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    平衡二叉树c++模版

    平衡二叉树是一种特殊类型的二叉树，它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这种数据结构的主要目的是为了保持数据的平衡分布，从而保证在插入、删除和查找操作中的效率。 ...

    平衡二叉树（增加-删除）

    用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能，目的是把二叉树的平衡算法记录在这里（备忘）。 目前只做了增加删除节点时二叉树自动平衡，保证这棵树什么时候都是平衡状态；如何将一棵不平衡的二叉树...

    数据结构平衡二叉树课程设计

    在IT领域，数据结构是计算机科学的基础，而平衡二叉树是其中一个重要概念，尤其对于高效的数据检索和存储。在这个“数据结构平衡二叉树课程设计”中，我们重点探讨了如何使用C语言实现平衡二叉树，并包含了课程设计...

    平衡二叉树时间复杂度计算1

    "平衡二叉树时间复杂度计算1" 在计算机科学中，平衡二叉树是一种特殊的二叉树数据结构，它的时间复杂度计算是非常重要的。下面我们将详细介绍平衡二叉树的时间复杂度计算。 首先，让我们了解什么是平衡二叉树。...

    2015广工数据结构实验--平衡二叉树(包含源码和实验报告

    平衡二叉树（Balanced Binary Tree）是数据结构中的一个重要概念，尤其在算法设计和数据库系统中发挥着关键作用。本实验是针对广东工业大学（简称“广工”）学生的一次数据结构课程实践，旨在让学生深入理解平衡...

    平衡二叉树操作的演示

    平衡二叉树是一种特殊的二叉树数据结构，其特性在于左右子树的高度差不超过1，这使得在树中的任何节点上进行查找、插入和删除操作的时间复杂度都能保证为O(log n)。AVL树是最早被提出的自平衡二叉搜索树，由G. M. ...

    平衡二叉树算法详细解释

    平衡二叉树是一种特殊的二叉树结构，它的主要特性是左右子树的高度差不超过1，保证了树的形态均匀，从而在查找、插入和删除等操作上的效率接近于最佳的二叉查找树。这种特性使得平衡二叉树在数据结构和算法中占有...

    平衡二叉树课程设计 课程设计

    平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树性质的同时，确保了左右子树的高度差不超过1。这样的结构使得在平衡二叉树中的搜索、插入和删除操作的时间复杂度都能保持在O(log n)的水平，大大提高了...

    数据结构课程设计——平衡二叉树的实现

    在数据结构课程设计中，平衡二叉树的实现是一个重要的实践环节，旨在加深对数据结构和算法的理解。平衡二叉树是一种特殊的二叉树，它确保了任何节点的两个子树的高度差不超过1，从而保证了操作如查找、插入和删除的...

    二叉树和平衡二叉树的C#实现源码

    二叉树和平衡二叉树是数据结构领域中的重要概念，尤其在计算机科学中，它们在数据存储、搜索和排序等方面发挥着关键作用。这里我们将深入探讨这两种数据结构及其C#实现。 首先，二叉树是一种特殊的树形数据结构，...

    平衡二叉树的演示操作（c语言）

    平衡二叉树是一种特殊的二叉树结构，它的左右两个子树的高度差不超过1，并且左右两个子树都是一棵平衡二叉树。这种数据结构在计算机科学中有着广泛的应用，尤其是在搜索、排序和数据存储等领域。本文将详细介绍平衡...

    平衡二叉树（纯C++实现）

    平衡二叉树是一种特殊的二叉树数据结构，其特性是左右子树的高度差不超过1，这使得在平衡二叉树中的查找、插入和删除操作的时间复杂度都能保持在O(log n)级别，大大提高了效率。在本项目中，我们将探讨如何使用C++...

    平衡二叉树数据结构课程设计

    平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树特性的同时，通过特定的结构调整策略，确保了树的高度平衡。这样的设计使得在平衡二叉树中执行插入、删除和查找等操作的时间复杂度可以保持为O(log n)，...

    平衡二叉树c++实现

    平衡二叉树是一种特殊的二叉树结构，它的左右子树高度差不超过1，且每个节点的左右子树都是平衡二叉树。这种设计使得在平衡二叉树中进行查找、插入和删除操作的时间复杂度可以达到O(log n)，极大地提高了数据操作的...

    二叉排序树与平衡二叉树的实现

    题　目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...

    生成平衡二叉树.cpp_C++_二叉树_数据结构_

    本话题将深入探讨“生成平衡二叉树”的概念，以及如何使用C++语言实现这一过程。平衡二叉树，如AVL树或红黑树，确保了树的高度平衡，从而在查找、插入和删除操作中保持较高的效率。 首先，我们需要了解平衡二叉树的...

    广工数据结构课程设计——平衡二叉树操作的演示

    广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...

    平衡二叉树遍历附源代码

    1. 利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找 插入和删除。 2 .初始，平衡二叉树为空树，操作界面给出查找，插入和删除三种操作供 选择，每种操作均要提示输入关键字，每次插入或删除...

Magicbox
Global site tag (gtag.js) - Google Analytics