I built a Binary Search Tree:
import random
class Node(object):
def __init__(self, key):
self.key = key
self.leftChild = None
self.rightChild = None
self.parent = None
def hasLeftChild(self):
if self.leftChild:
return True
else:
return False
def hasRightChild(self):
if self.rightChild:
return True
else:
return False
def isLeftChild(self):
if self.parent.leftChild == self:
return True
else:
return False
def isRightChild(self):
if self.parent.rightChild == self:
return True
else:
return False
def isRoot(self):
if not self.parent:
return True
else:
return False
class BinaryTree(object):
def __init__(self):
self.root = None
self.storage = 0
def addNode(self, newItem):
if self.storage == 0:
self.root = Node(newItem)
else:
currentNode = self.root
self.__addNode(currentNode, newItem)
self.storage += 1
def __addNode(self, currentNode, newItem):
if newItem < currentNode.key:
if currentNode.hasLeftChild():
self.__addNode(currentNode.leftChild, newItem)
else:
currentNode.leftChild = Node(newItem)
currentNode.leftChild.parent = currentNode
if newItem > currentNode.key:
if currentNode.hasRightChild():
self.__addNode(currentNode.rightChild, newItem)
else:
currentNode.rightChild = Node(newItem)
currentNode.rightChild.parent = self
def findNode(self, searchKey):
if self.storage == 0:
return None
else:
if self.root.key == searchKey:
return self.root
else:
currentNode = self.root
return self.__findNode(currentNode, searchKey)
def __findNode(self, currentNode, searchKey):
if searchKey == currentNode.key:
return currentNode
if searchKey < currentNode.key:
if currentNode.hasLeftChild():
return self.__findNode(currentNode.leftChild, searchKey)
if searchKey > currentNode.key:
if currentNode.hasRightChild():
return self.__findNode(currentNode.rightCHild, searchKey)
return None
def getRandomNode(self):
randomNum = random.randrange(self.storage)
currentNode = self.root
self.__getRandomNode(currentNode, randomNum)
def __getRandomNode(self, currentNode, numCount):
if numCount == 0:
print('Find node {0}'.format(currentNode.key))
return currentNode, numCount
else:
if currentNode.hasLeftChild():
numCount -= 1
node, numCount = self.__getRandomNode(currentNode.leftChild, numCount)
if currentNode.hasRightChild():
numCount -= 1
node, numCount = self.__getRandomNode(currentNode.rightChild, numCount)
return None, numCount
print('-----Add Node to BTree-----')
myBinaryTree = BinaryTree()
myBinaryTree.addNode(15)
myBinaryTree.addNode(10)
myBinaryTree.addNode(20)
myBinaryTree.addNode(9)
myBinaryTree.addNode(13)
myBinaryTree.addNode(12)
print('-----Get Random Node-----')
myBinaryTree.getRandomNode()
When I was building the getRandom recursive function, for some of reason, I can only print(make finding random node logically work). But this is really not my main purpose, my main purpose is return the "random node" Anyone can help me modified the getRandom function and let the "return Node" really work ?
Thanks
Aucun commentaire:
Enregistrer un commentaire