- 浏览: 13454 次
- 性别:
- 来自: 上海
最近访客 更多访客>>
最新评论
-
huochai2009:
python 这么强大?
social game server端开发的哪些事儿 -
ilicis:
范三山 写道你们的是amf或rtmp还是自己的协议?自己的协议 ...
social game server端开发的哪些事儿 -
范三山:
你们的是amf或rtmp还是自己的协议?
social game server端开发的哪些事儿
#!/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
没想到还可以现在用来交作业。。。
说不定将来会用上
相关推荐
平衡二叉树是一种特殊类型的二叉树,它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这种数据结构的主要目的是为了保持数据的平衡分布,从而保证在插入、删除和查找操作中的效率。 ...
用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能,目的是把二叉树的平衡算法记录在这里(备忘)。 目前只做了增加删除节点时二叉树自动平衡,保证这棵树什么时候都是平衡状态;如何将一棵不平衡的二叉树...
在IT领域,数据结构是计算机科学的基础,而平衡二叉树是其中一个重要概念,尤其对于高效的数据检索和存储。在这个“数据结构平衡二叉树课程设计”中,我们重点探讨了如何使用C语言实现平衡二叉树,并包含了课程设计...
"平衡二叉树时间复杂度计算1" 在计算机科学中,平衡二叉树是一种特殊的二叉树数据结构,它的时间复杂度计算是非常重要的。下面我们将详细介绍平衡二叉树的时间复杂度计算。 首先,让我们了解什么是平衡二叉树。...
平衡二叉树(Balanced Binary Tree)是数据结构中的一个重要概念,尤其在算法设计和数据库系统中发挥着关键作用。本实验是针对广东工业大学(简称“广工”)学生的一次数据结构课程实践,旨在让学生深入理解平衡...
平衡二叉树是一种特殊的二叉树数据结构,其特性在于左右子树的高度差不超过1,这使得在树中的任何节点上进行查找、插入和删除操作的时间复杂度都能保证为O(log n)。AVL树是最早被提出的自平衡二叉搜索树,由G. M. ...
平衡二叉树是一种特殊的二叉树结构,它的主要特性是左右子树的高度差不超过1,保证了树的形态均匀,从而在查找、插入和删除等操作上的效率接近于最佳的二叉查找树。这种特性使得平衡二叉树在数据结构和算法中占有...
平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树性质的同时,确保了左右子树的高度差不超过1。这样的结构使得在平衡二叉树中的搜索、插入和删除操作的时间复杂度都能保持在O(log n)的水平,大大提高了...
在数据结构课程设计中,平衡二叉树的实现是一个重要的实践环节,旨在加深对数据结构和算法的理解。平衡二叉树是一种特殊的二叉树,它确保了任何节点的两个子树的高度差不超过1,从而保证了操作如查找、插入和删除的...
二叉树和平衡二叉树是数据结构领域中的重要概念,尤其在计算机科学中,它们在数据存储、搜索和排序等方面发挥着关键作用。这里我们将深入探讨这两种数据结构及其C#实现。 首先,二叉树是一种特殊的树形数据结构,...
平衡二叉树是一种特殊的二叉树结构,它的左右两个子树的高度差不超过1,并且左右两个子树都是一棵平衡二叉树。这种数据结构在计算机科学中有着广泛的应用,尤其是在搜索、排序和数据存储等领域。本文将详细介绍平衡...
平衡二叉树是一种特殊的二叉树数据结构,其特性是左右子树的高度差不超过1,这使得在平衡二叉树中的查找、插入和删除操作的时间复杂度都能保持在O(log n)级别,大大提高了效率。在本项目中,我们将探讨如何使用C++...
平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树特性的同时,通过特定的结构调整策略,确保了树的高度平衡。这样的设计使得在平衡二叉树中执行插入、删除和查找等操作的时间复杂度可以保持为O(log n),...
平衡二叉树是一种特殊的二叉树结构,它的左右子树高度差不超过1,且每个节点的左右子树都是平衡二叉树。这种设计使得在平衡二叉树中进行查找、插入和删除操作的时间复杂度可以达到O(log n),极大地提高了数据操作的...
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
本话题将深入探讨“生成平衡二叉树”的概念,以及如何使用C++语言实现这一过程。平衡二叉树,如AVL树或红黑树,确保了树的高度平衡,从而在查找、插入和删除操作中保持较高的效率。 首先,我们需要了解平衡二叉树的...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括: [实现提示] (1) 初始,平衡二叉树为空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
1. 利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找 插入和删除。 2 .初始,平衡二叉树为空树,操作界面给出查找,插入和删除三种操作供 选择,每种操作均要提示输入关键字,每次插入或删除...