当前位置: 首页 > python算法游戏 > 使用二叉排序树

使用二叉排序树

 Python |  复制 |? 
001
#encoding=utf8
002
 
003
'''
004
B+树中的节点。其中value为当前节点值。
005
lNode为左孩子节点,rNode为右孩子节点,count为重复数量
006
'''
007
class TNode(object):
008
    def __init__(self,value,lnode=None,rnode=None,count=1):
009
        self.value = value
010
        self.lNode = lnode
011
        self.rNode = rnode
012
        self.count = count
013
 
014
    def setLNode(self,node):
015
        self.lNode = node
016
 
017
    def setRNode(self,node):
018
        self.rNode = node
019
 
020
    def getLNode(self):
021
        return self.lNode
022
 
023
    def getRNode(self):
024
        return self.rNode
025
 
026
    def addCount(self):
027
        self.count = self.count+1
028
 
029
    def getCount(self):
030
        return self.count
031
 
032
    def setValue(self,value):
033
        self.value = value
034
 
035
    def getValue(self):
036
        return self.value
037
 
038
'''
039
二叉搜索树,在这里用作排序,实际就是一个普通的二叉树。
040
初始化时,加入一个root节点
041
addNode方法:
042
当新加入一个节点,则从根节点开始比较,
043
与根节点值相同,则将根节点count+1,
044
大于根节点值,则将其与根节点的右子节点重新开始比较
045
小于根节点值,则将其与根节点的左子节点重新开始比较
046
递归完成。
047
printTree方法:
048
打印中序遍历树结果。
049
'''
050
class BSTSort(object):
051
    def __init__(self,node):
052
        self.root = node
053
 
054
    def addNode(self,node):
055
        currentNode = self.root
056
        while currentNode != None:
057
            currentValue = currentNode.getValue()
058
            insertValue = node.getValue()
059
            if currentValue == insertValue :
060
                currentNode.addCount()
061
                break
062
            elif currentValue > insertValue :
063
                if currentNode.getLNode() != None :
064
                    currentNode = currentNode.getLNode()
065
                else:
066
                    currentNode.setLNode(node)
067
                    break
068
            else:
069
                if currentNode.getRNode() != None:
070
                    currentNode = currentNode.getRNode()
071
                else:
072
                    currentNode.setRNode(node)
073
                    break
074
 
075
    def printTree(self,fromNode):
076
        if fromNode == None:
077
            fromNode = self.root
078
        lNode = fromNode.getLNode()
079
        rNode = fromNode.getRNode()
080
        if lNode != None:
081
            self.printTree(lNode)
082
        for i in range(0,fromNode.getCount()):
083
            print fromNode.getValue()
084
        if rNode != None:
085
            self.printTree(rNode)
086
 
087
    def getSortList(self,fromNode,list):    
088
        if fromNode == None:
089
            fromNode = self.root
090
        lNode = fromNode.getLNode()
091
        rNode = fromNode.getRNode()
092
        if lNode != None:
093
            self.getSortList(lNode, list)
094
        for i in range(0,fromNode.getCount()):
095
            list.append(fromNode.getValue())
096
        if rNode != None:
097
            self.getSortList(rNode, list)
098
        return list          
099
 
100
list = [19,283,0,-2,-3,89,76,3,5,9,19,879,627,-29,-987,-877,0,0,0]
101
rootNode = TNode(list[0])
102
bst = BSTSort(rootNode)
103
for i in range(1,len(list)):
104
    tmpNode = TNode(list[i])
105
    bst.addNode(tmpNode)
106
 
107
#bst.printTree(rootNode)
108
list = []
109
bst.getSortList(rootNode, list)
110
print list       
111



本文固定链接: http://anyoneking.com/archives/35 | 懒散狂徒的博客
标签: ,

【上一篇】
【下一篇】

使用二叉排序树:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!