Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class TreeNode:
- def __init__(self, key, left=None, right=None, parent=None):
- self.key = key
- self.leftChild = left
- self.rightChild = right
- self.parent = parent
- def hasLeftChild(self):
- return self.leftChild
- def hasRightChild(self):
- return self.rightChild
- def isLeftChild(self):
- return self.parent and self.parent.leftChild == self
- def isRightChild(self):
- return self.parent and self.parent.rightChild == self
- def isRoot(self):
- return not self.parent
- def isLeaf(self):
- return not (self.rightChild or self.leftChild)
- def hasAnyChildren(self):
- return self.rightChild or self.leftChild
- def hasBothChildren(self):
- return self.rightChild and self.leftChild
- def replaceNodeData(self, key, lc, rc):
- self.key = key
- self.leftChild = lc
- self.rightChild = rc
- if self.hasLeftChild():
- self.leftChild.parent = self
- if self.hasRightChild():
- self.rightChild.parent = self
- class BinarySearchTree:
- def __init__(self):
- self.root = None
- self.size = 0
- def length(self):
- return self.size
- def __len__(self):
- return self.size
- def put(self, key):
- if self.root:
- self._put(key, self.root)
- else:
- self.root = TreeNode(key)
- self.size = self.size + 1
- def _put(self, key, currentNode):
- if key < currentNode.key:
- if currentNode.hasLeftChild():
- self._put(key, currentNode.leftChild)
- else:
- currentNode.leftChild = TreeNode(key, parent=currentNode)
- else:
- if currentNode.hasRightChild():
- self._put(key, currentNode.rightChild)
- else:
- currentNode.rightChild = TreeNode(key, parent=currentNode)
- def __setitem__(self, k):
- self.put(k)
- def get(self, key):
- if self.root:
- res = self._get(key, self.root)
- if res:
- return res.payload
- else:
- return None
- else:
- return None
- def _get(self, key, currentNode):
- if not currentNode:
- return None
- elif currentNode.key == key:
- return currentNode
- elif key < currentNode.key:
- return self._get(key, currentNode.leftChild)
- else:
- return self._get(key, currentNode.rightChild)
- def __getitem__(self, key):
- return self.get(key)
- def __contains__(self, key):
- if self._get(key, self.root):
- return True
- else:
- return False
- def delete(self, key):
- if self.size > 1:
- nodeToRemove = self._get(key, self.root)
- if nodeToRemove:
- self.remove(nodeToRemove)
- self.size = self.size - 1
- else:
- raise KeyError('Error, key not in tree')
- elif self.size == 1 and self.root.key == key:
- self.root = None
- self.size = self.size - 1
- else:
- raise KeyError('Error, key not in tree')
- def __delitem__(self, key):
- self.delete(key)
- def spliceOut(self):
- if self.isLeaf():
- if self.isLeftChild():
- self.parent.leftChild = None
- else:
- self.parent.rightChild = None
- elif self.hasAnyChildren():
- if self.hasLeftChild():
- if self.isLeftChild():
- self.parent.leftChild = self.leftChild
- else:
- self.parent.rightChild = self.leftChild
- self.leftChild.parent = self.parent
- else:
- if self.isLeftChild():
- self.parent.leftChild = self.rightChild
- else:
- self.parent.rightChild = self.rightChild
- self.rightChild.parent = self.parent
- def findSuccessor(self):
- succ = None
- if self.root.hasRightChild():
- succ = self.findMin()
- else:
- if self.parent:
- if self.isLeftChild():
- succ = self.parent
- else:
- self.parent.rightChild = None
- succ = self.parent.findSuccessor()
- self.parent.rightChild = self
- return succ
- def findMin(self):
- current = self.root
- while current.hasLeftChild():
- current = current.leftChild
- return current.key
- def findMax(self):
- current = self.root
- while current.hasRightChild():
- current = current.rightChild
- return current.key
- def remove(self, currentNode):
- if currentNode.isLeaf(): # leaf
- if currentNode == currentNode.parent.leftChild:
- currentNode.parent.leftChild = None
- else:
- currentNode.parent.rightChild = None
- elif currentNode.hasBothChildren(): # interior
- succ = currentNode.findSuccessor()
- succ.spliceOut()
- currentNode.key = succ.key
- else: # this node has one child
- if currentNode.hasLeftChild():
- if currentNode.isLeftChild():
- currentNode.leftChild.parent = currentNode.parent
- currentNode.parent.leftChild = currentNode.leftChild
- elif currentNode.isRightChild():
- currentNode.leftChild.parent = currentNode.parent
- currentNode.parent.rightChild = currentNode.leftChild
- else:
- currentNode.replaceNodeData(currentNode.leftChild.key,
- currentNode.leftChild.leftChild,
- currentNode.leftChild.rightChild)
- else:
- if currentNode.isLeftChild():
- currentNode.rightChild.parent = currentNode.parent
- currentNode.parent.leftChild = currentNode.rightChild
- elif currentNode.isRightChild():
- currentNode.rightChild.parent = currentNode.parent
- currentNode.parent.rightChild = currentNode.rightChild
- else:
- currentNode.replaceNodeData(currentNode.rightChild.key,
- currentNode.rightChild.leftChild,
- currentNode.rightChild.rightChild)
- def direct(self):
- current = self.root
- self.directHelp(current)
- def directHelp(self, current):
- print(current.key)
- if current.hasLeftChild():
- self.directHelp(current.leftChild)
- if current.hasRightChild():
- self.directHelp(current.rightChild)
- def symmetric(self):
- current = self.root
- self.symmetricHelp(current)
- def symmetricHelp(self, current):
- if current.hasLeftChild():
- self.symmetricHelp(current.leftChild)
- print(current.key)
- if current.hasRightChild():
- self.symmetricHelp(current.rightChild)
- def back(self):
- current = self.root
- self.backHelp(current)
- def backHelp(self, current):
- if current.hasLeftChild():
- self.backHelp(current.leftChild)
- if current.hasRightChild():
- self.backHelp(current.rightChild)
- print(current.key)
- def deletedHelp(self, p, current):
- if current.hasLeftChild():
- self.delHelp(current.leftChild)
- if current.hasRightChild():
- self.delHelp(current.rightChild)
- if current.key == p:
- self.delete(current.key)
- def deleted(self, p):
- current = self.root
- self.deletedHelp(current, p)
- def delpar(self):
- current = self.root
- self.delHelp(current)
- def delHelp(self, current):
- if current.hasLeftChild():
- self.delHelp(current.leftChild)
- if current.hasRightChild():
- self.delHelp(current.rightChild)
- if current.key % 2 == 0:
- self.delete(current.key)
- def countOfEl(self, val):
- current = self.root
- i=0
- return self.countOfElHelp(current, val, i)
- def countOfElHelp(self, current, val, i):
- if current.hasLeftChild():
- i=self.countOfElHelp(current.leftChild, val, i)
- if current.hasRightChild():
- i=self.countOfElHelp(current.rightChild, val, i)
- if current.key == val:
- i+=1
- return i
- def sum(self):
- current = self.root
- i=0
- return self.sumHelp(current, i)
- def sumHelp(self, current, i):
- if current.hasLeftChild():
- i=self.sumHelp(current.leftChild, i)
- if current.hasRightChild():
- i=self.sumHelp(current.rightChild, i)
- i += current.key
- return i
- #from tree import *
- a = BinarySearchTree()
- print ('1. Добавить элемент.')
- print ('2. Удалить введенный элемент.')
- print ('3. Максимальное значение.')
- print ('4. Минимальное значение.')
- print ('5. Удалить все парные элементы.')
- print ('6. Количество элементов в дереве.')
- print ('7. Сумма всех элементов.')
- print ('8. Симметрический обход.')
- print ('9. Количество повторений элемента в дереве.')
- print ('10. Обратный обход.')
- print ('11. Прямой обход.')
- def pr():
- k = int(input('enter: '))
- if k == 1:
- p = int(input('Введите элемент, который хотите добавить в дерево: '))
- a.put(p)
- pr()
- elif k == 2:
- d = int(input('Какой элемент Вы хотели бы удалить из дерева? '))
- a.delete(d)
- pr()
- elif k == 3:
- print(a.findMax())
- pr()
- elif k == 4:
- print(a.findMin())
- pr()
- elif k == 5:
- a.delpar()
- pr()
- elif k == 6:
- print(a.length())
- pr()
- elif k == 7:
- print(a.sum())
- pr()
- elif k == 8:
- print (a.symmetric())
- pr()
- elif k == 9:
- o = int(input('Введите интересующее Вас значение: '))
- print(a.countOfEl(o))
- pr()
- elif k == 10:
- print (a.back())
- pr()
- elif k == 11:
- print (a.direct())
- pr()
- else:
- print ('Такого пункта меню нет:(')
- pr()
- pr()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement