Binary search tree

Binary search tree definition

   Binary search tree (Binary Search Tree), Also known as binary sorting tree (Binary Sort Tree).
   A binary search tree is a binary tree with the following properties ：
  （1） If left subtree is not empty , Then the values of all nodes on the left subtree are less than or equal to the values of its root nodes .
  （2） If the right subtree is not empty , Then the value of all nodes on the right subtree is greater than or equal to the value of its root node .
  （3） Left 、 The right subtree is also a binary search tree .

class TreeNode:
	''' Definition of binary search tree node '''
	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class OperationTree:
	''' Binary search tree operation '''
	def insert(self, root, val):
		''' Binary search tree insertion operation '''
		if root == None:
			root = TreeNode(val)
		elif val < root.val:
			root.left = self.insert(root.left, val)
		elif val > root.val:
			root.right = self.insert(root.right, val)
		return root

	def query(self, root, val):
		''' Binary search tree query operation '''
		if root == None:
			return False
		if root.val == val:
			return True
		elif val < root.val:
			return self.query(root.left, val)
		elif val > root.val:
			return self.query(root.right, val)

	def findMin(self, root):
		''' Find the minimum value point in the binary search tree '''
		if root.left:
			return self.findMin(root.left)
		else:
			return root

	def findMax(self, root):
		''' Find the maximum point in the binary search tree '''
		if root.right:
			return self.findMax(root.right)
		else:
			return root

	def delNode(self, root, val):
		''' Delete the median value of binary search tree as val The point of '''
		if root == None:
			return 
		if val < root.val:
			root.left = self.delNode(root.left, val)
		elif val > root.val:
			root.right = self.delNode(root.right, val)
		#  When val == root.val when , There are three situations ： Only the left subtree or only the right subtree 、 There are left and right subtrees 、 There is neither left subtree nor right subtree 
		else:
			if root.left and root.right:
				#  There are both left and right subtrees , You need to find the minimum node in the right subtree 
				temp = self.findMin(root.right)
				root.val = temp.val
				#  Then delete the minimum node in the right subtree 
				root.right = self.delNode(root.right, temp.val)
			elif root.right == None and root.left == None:
				#  Left and right subtrees are empty 
				root = None
			elif root.right == None:
				#  Only the left sub tree 
				root = root.left
			elif root.left == None:
				#  Only the right subtree 
				root = root.right
		return root

	def printTree(self, root):
		#  Print binary search tree ( Medium order printing , An orderly sequence of numbers )
		if root == None:
			return 
		self.printTree(root.left)
		print(root.val, end = ' ')
		self.printTree(root.right)

if __name__ == '__main__':
	List = [17,5,35,2,11,29,38,9,16,8]
	root = None
	op = OperationTree()
	for val in List:
		root = op.insert(root,val)
	print(' Print binary search tree in middle order ：', end = ' ')
	op.printTree(root)
	print('')
	print(' The value of the root node is ：', root.val)
	print(' The maximum value in the tree is :', op.findMax(root).val)
	print(' The minimum value in the tree is :', op.findMin(root).val)
	print(' The value in the query tree is 5 The node of :', op.query(root, 5))
	print(' The value in the query tree is 100 The node of :', op.query(root, 100))
	print(' The value in the delete tree is 16 The node of :', end = ' ')
	root = op.delNode(root, 16)
	op.printTree(root)
	print('')
	print(' The value in the delete tree is 5 The node of :', end = ' ')
	root = op.delNode(root, 5)
	op.printTree(root)
	print('')