TA貢獻(xiàn)1848條經(jīng)驗(yàn) 獲得超2個(gè)贊
這是二進(jìn)制搜索樹(shù)的簡(jiǎn)單遞歸實(shí)現(xiàn)。
#!/usr/bin/python
class Node:
def __init__(self, val):
self.l = None
self.r = None
self.v = val
class Tree:
def __init__(self):
self.root = None
def getRoot(self):
return self.root
def add(self, val):
if(self.root == None):
self.root = Node(val)
else:
self._add(val, self.root)
def _add(self, val, node):
if(val < node.v):
if(node.l != None):
self._add(val, node.l)
else:
node.l = Node(val)
else:
if(node.r != None):
self._add(val, node.r)
else:
node.r = Node(val)
def find(self, val):
if(self.root != None):
return self._find(val, self.root)
else:
return None
def _find(self, val, node):
if(val == node.v):
return node
elif(val < node.v and node.l != None):
self._find(val, node.l)
elif(val > node.v and node.r != None):
self._find(val, node.r)
def deleteTree(self):
# garbage collector will do this for us.
self.root = None
def printTree(self):
if(self.root != None):
self._printTree(self.root)
def _printTree(self, node):
if(node != None):
self._printTree(node.l)
print str(node.v) + ' '
self._printTree(node.r)
# 3
# 0 4
# 2 8
tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print (tree.find(3)).v
print tree.find(10)
tree.deleteTree()
tree.printTree()
TA貢獻(xiàn)1936條經(jīng)驗(yàn) 獲得超7個(gè)贊
# simple binary tree
# in this implementation, a node is inserted between an existing node and the root
class BinaryTree():
def __init__(self,rootid):
self.left = None
self.right = None
self.rootid = rootid
def getLeftChild(self):
return self.left
def getRightChild(self):
return self.right
def setNodeValue(self,value):
self.rootid = value
def getNodeValue(self):
return self.rootid
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
tree = BinaryTree(newNode)
tree.right = self.right
self.right = tree
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
tree = BinaryTree(newNode)
tree.left = self.left
self.left = tree
def printTree(tree):
if tree != None:
printTree(tree.getLeftChild())
print(tree.getNodeValue())
printTree(tree.getRightChild())
# test tree
def testTree():
myTree = BinaryTree("Maud")
myTree.insertLeft("Bob")
myTree.insertRight("Tony")
myTree.insertRight("Steven")
printTree(myTree)
在此處了解更多信息：-這是二進(jìn)制樹(shù)的非常簡(jiǎn)單的實(shí)現(xiàn)。
TA貢獻(xiàn)1810條經(jīng)驗(yàn) 獲得超4個(gè)贊
BST在Python中的簡(jiǎn)單實(shí)現(xiàn)
class TreeNode:
def __init__(self, value):
self.left = None
self.right = None
self.data = value
class Tree:
def __init__(self):
self.root = None
def addNode(self, node, value):
if(node==None):
self.root = TreeNode(value)
else:
if(value<node.data):
if(node.left==None):
node.left = TreeNode(value)
else:
self.addNode(node.left, value)
else:
if(node.right==None):
node.right = TreeNode(value)
else:
self.addNode(node.right, value)
def printInorder(self, node):
if(node!=None):
self.printInorder(node.left)
print(node.data)
self.printInorder(node.right)
def main():
testTree = Tree()
testTree.addNode(testTree.root, 200)
testTree.addNode(testTree.root, 300)
testTree.addNode(testTree.root, 100)
testTree.addNode(testTree.root, 30)
testTree.printInorder(testTree.root)
舉報(bào)