Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Nom : Implémentation objet d'un arbre binaire de recherche et d'un noeud
- Développeur : Ander Arrosteguy
- Date de mise à jour : 23/09/2019
- """
- class BinarySearchTree:
- root = None
- size = 0
- internal_lc = 0
- external_lc = 0
- def __init__(self, root = None):
- if (self.root != None):
- self.size += 1
- self.root = root
- #################################
- def setRoot(self, root = None):
- self.root = root
- def setSize(self, size):
- self.size = size
- def setInternalLc(self, internal_lc):
- self.internal_lc = internal_lc
- def setExternalLc(self, external_lc):
- self.external_lc = external_lc
- #################################
- def getRoot(self):
- return self.root
- def getHeight(self):
- return self.getRoot().getHeight()
- def getSize(self):
- return self.size
- def getInternalLc(self):
- return self.internal_lc
- def getExternalLc(self):
- return self.external_lc
- #################################
- def addNode(self, node, base = None):
- if (not self.hasRoot()):
- self.setRoot(node)
- return
- if (base == None):
- base = self.getRoot()
- if (node.getValue() <= base.getValue()):
- if (not base.hasLeftChild()):
- base.addLeftChild(node)
- return
- else:
- self.addNode(node, base.getLeftChild())
- else:
- if (not base.hasRightChild()):
- base.addRightChild(node)
- return
- else:
- self.addNode(node, root.getRightChild())
- self.setSize(self.getSize() + 1)
- # Todo
- def removeNode(self, node):
- self.setSize(self.getSize() - 1)
- def hasRoot(self):
- return (self.root != None)
- def getLc(self):
- return (self.getExternalLc() + self.internal_lc)
- def getTreeHeight(self):
- return self.getRoot().getHeight()
- class Node:
- value = 0
- parent = None
- leftChild = None
- rightChild = None
- def __init__(self, value, parent = None, leftChild = None, rightChild = None):
- self.value = value
- self.parent = parent
- self.leftChild = leftChild
- self.rightChild = rightChild
- #################################
- def setValue(self, value):
- self.value = value
- def setParent(self, parent = None):
- self.parent = parent
- def addLeftChild(self, leftChild):
- self.leftChild = leftChild
- def removeLeftChild(self):
- self.leftChild = None
- def addRightChild(self, rightChild):
- self.rightChild = rightChild
- def removeRightChild(self):
- self.rightChild = None
- #################################
- def getValue(self):
- return self.value
- def getParent(self):
- return self.parent
- def getLeftChild(self):
- return self.leftChild
- def getRightChild(self):
- return self.rightChild
- #################################
- def isRoot(self):
- return (self.getParent() == None)
- def isLeaf(self):
- return not self.hasChildren()
- def isBranch(self):
- return self.hasChildren()
- def hasLeftChild(self):
- return (self.getLeftChild() != None)
- def hasRightChild(self):
- return (self.getRightChild() != None)
- def hasChildren(self):
- return ((self.getLeftChild() != None) or (self.getRightChild() != None))
- def getHeight(self):
- if (not self.hasChildren()):
- return 0
- heightLeft = 0
- heightRight = 0
- if (self.hasLeftChild()):
- heightLeft = self.getLeftChild().getHeight() + 1
- if (self.hasRightChild()):
- heightRight = self.getRightChild().getHeight() + 1
- if (heightLeft > heightRight): return heightLeft
- else: return heightRight
- def factorBalance(self):
- return (self.getRightChild().getHeight() - self.getLeftChild().getHeight())
- if (__name__ == "__main__"):
- tree = BinarySearchTree()
- root = Node(5)
- tree.addNode(root)
- tree.addNode(Node(3))
- tree.addNode(Node(4))
- tree.addNode(Node(6))
- tree.addNode(Node(14))
- print(tree.getRoot().getRightChild().getRightChild().getValue())
- print(tree.getHeight())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement