samedi 29 avril 2017

Python3, get random node from Binary Tree

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