fork download
copy 
  1. from copy import copy, deepcopy
  2.  
  3.  
  4. class Node:
  5.     def __init__(self, data=None):
  6.         self.data = data
  7.         self.left = None
  8.         self.right = None
  9.  
  10.     def __copy__(self):
  11.         new_node = Node(self.data)
  12.  
  13.         if self.left is not None:
  14.             new_node.left = copy(self.left)
  15.  
  16.         if self.right is not None:
  17.             new_node.right = copy(self.right)
  18.  
  19.         return new_node
  20.  
  21.  
  22.     def __deepcopy__(self, memo):
  23.         if id(self) in memo:
  24.             return memo[id(self)]
  25.  
  26.         new_node = Node(self.data)
  27.  
  28.         memo[id(self)] = new_node
  29.  
  30.         new_node.left = deepcopy(self.left, memo)
  31.         new_node.right = deepcopy(self.right, memo)
  32.  
  33.         return new_node
  34.  
  35.  
  36. class BST:
  37.     def __init__(self, values=None):
  38.  
  39.         self.root = None
  40.  
  41.         if isinstance(values, list):
  42.  
  43.             for value in values:
  44.  
  45.                 if type(value) == int:
  46.                     self.insert(value)
  47.  
  48.                 else:
  49.                     raise ValueError("BST chỉ nhận số nguyên")
  50.  
  51.         elif isinstance(values, str):
  52.  
  53.             value = None
  54.  
  55.             for x in values:
  56.  
  57.                 if '0' <= x <= '9':
  58.  
  59.                     if value is None:
  60.                         value = 0
  61.  
  62.                     value = value * 10 + (ord(x) - ord('0'))
  63.  
  64.                 elif x == ' ' or x == ',':
  65.  
  66.                     if value is not None:
  67.                         self.insert(value)
  68.                         value = None
  69.  
  70.                 else:
  71.                     raise ValueError("Ký tự không hợp lệ")
  72.  
  73.             if value is not None:
  74.                 self.insert(value)
  75.  
  76.  
  77.         elif values is None:
  78.             self.root = None
  79.  
  80.         else:
  81.             raise ValueError("Input không hợp lệ")
  82.  
  83.     def insert(self, value):
  84.  
  85.         self.root = self._insert(self.root, value)
  86.  
  87.     def _insert(self, node, value):
  88.  
  89.         if node is None:
  90.             return Node(value)
  91.  
  92.         if value < node.data:
  93.             node.left = self._insert(node.left, value)
  94.  
  95.         else:
  96.             node.right = self._insert(node.right, value)
  97.  
  98.         return node
  99.  
  100.     def remove(self, value):
  101.  
  102.         self.root = self._remove(self.root, value)
  103.  
  104.     def _remove(self, node, value):
  105.  
  106.         if node is None:
  107.             return None
  108.  
  109.         # tìm node cần xóa
  110.  
  111.         if value < node.data:
  112.  
  113.             node.left = self._remove(node.left, value)
  114.  
  115.         elif value > node.data:
  116.  
  117.             node.right = self._remove(node.right, value)
  118.  
  119.         else:
  120.  
  121.             # ===== CASE 1: node lá =====
  122.  
  123.             if node.left is None and node.right is None:
  124.                 return None
  125.  
  126.             # ===== CASE 2: có 1 con =====
  127.  
  128.             if node.left is None:
  129.                 return node.right
  130.  
  131.             if node.right is None:
  132.                 return node.left
  133.  
  134.             # ===== CASE 3: có 2 con =====
  135.  
  136.             successor = self._min(node.right)
  137.  
  138.             node.data = successor.data
  139.  
  140.             node.right = self._remove(node.right, successor.data)
  141.  
  142.         return node
  143.  
  144.     def _min(self, node):
  145.  
  146.         while node.left is not None:
  147.             node = node.left
  148.  
  149.         return node
  150.  
  151.     def inorder(self):
  152.  
  153.         self._inorder(self.root)
  154.  
  155.         print()
  156.  
  157.     def _inorder(self, node):
  158.  
  159.         if node is None:
  160.             return
  161.  
  162.         self._inorder(node.left)
  163.  
  164.         print(node.data, end=' ')
  165.  
  166.         self._inorder(node.right)
  167.  
  168.     def __copy__(self):
  169.  
  170.         new_bst = BST()
  171.  
  172.         if self.root is not None:
  173.             new_bst.root = copy(self.root)
  174.  
  175.         return new_bst
  176.  
  177.     def __deepcopy__(self, memo):
  178.  
  179.         if id(self) in memo:
  180.             return memo[id(self)]
  181.  
  182.         new_bst = BST()
  183.  
  184.         memo[id(self)] = new_bst
  185.  
  186.         new_bst.root = deepcopy(self.root, memo)
  187.  
  188.         return new_bst
  189.  
  190.  
  191.     def __iter__(self):
  192.         yield from self._iter_inorder(self.root)
  193.  
  194.  
  195.     def _iter_inorder(self, node):
  196.  
  197.         if node is None:
  198.             return
  199.  
  200.         yield from self._iter_inorder(node.left)
  201.  
  202.         yield node.data
  203.  
  204.         yield from self._iter_inorder(node.right)
  205.  
  206.     def __getitem__(self, key):
  207.  
  208.         values = list(self)
  209.  
  210.         if isinstance(key, slice):
  211.  
  212.             new_values = values[key]
  213.  
  214.             return BST(new_values)
  215.  
  216.         return values[key]
  217.  
  218.  
  219. class vector3D(object):
  220. 	"""docstring for vector3D"""
  221. 	def __init__(self, x, y, z):
  222. 		super(vector3D, self).__init__()
  223. 		self.x = x
  224. 		self.y = y
  225. 		self.z = z
  226.  
  227. 	def __str__(self):
  228. 		return f"[{self.x}, {self.y}, {self.z}]"
  229.  
  230. 	def __add__(self, other):
  231. 		if isinstance(other, vector3D):
  232. 			return vector3D(self.x + other.x, self.y + other.y, self.z + other.z)
  233. 		else:
  234. 			return vector3D(self.x, self.y, self.z)
  235.  
  236. 	def __radd__(self, other):
  237. 		return self.__add__(other)
  238.  
  239. 	def __neg__(self):
  240. 		return vector3D(- self.x, - self.y, - self.z)
  241.  
  242. 	def __mul__(self, other):
  243. 		if isinstance(other, vector3D):
  244. 			return (self.x * other.x) + (self.y * other.y) + (self.z * other.z)
  245. 		elif isinstance(other, (int, float)):
  246. 			return vector3D(self.x * other, self.y * other, self.z * other)
  247. 		else:
  248. 			return vector3D(self.x, self.y, self.z)
  249.  
  250. 	def __rmul__(self, other):
  251. 		return self.__mul__(other)
  252.  
  253. 	def __iter__(self):
  254. 		return iter(f"{self.x}{self.y}{self.z}")
  255.  
Success #stdin #stdout 0.1s 14108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p6O3Js
oop_python
language:
Python 3 (python  3.12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!