Created
March 17, 2021 17:32
-
-
Save alejolp/851591159f037bf4e72f681fd1298db9 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class TreeNode: | |
| def __init__(self, value, left, right): | |
| self.value = value | |
| self.left = left | |
| self.right = right | |
| class BinarySearchTree: | |
| def __init__(self): | |
| self.root = None | |
| def BST_insert(bst, node): | |
| # ITERATIVE | |
| if bst.root == None: | |
| bst.root = node | |
| else: | |
| aux = bst.root | |
| while True: | |
| if node.value < aux.value: | |
| if aux.left == None: | |
| aux.left = node | |
| break | |
| else: | |
| aux = aux.left | |
| else: | |
| if aux.right == None: | |
| aux.right = node | |
| break | |
| else: | |
| aux = aux.right | |
| def BST_insert_rec_node(root, node): | |
| # INSERT RECURSIVE | |
| if root is None: | |
| return node | |
| elif node.value < root.value: | |
| root.left = BST_insert_rec_node(root.left, node) | |
| else: | |
| root.right = BST_insert_rec_node(root.right, node) | |
| return root | |
| def BST_insert_rec(bst, node): | |
| bst.root = BST_insert_rec_node(bst.root, node) | |
| def BST_inorder_node(node): | |
| if node: | |
| BST_inorder_node(node.left) | |
| print(node.value) | |
| BST_inorder_node(node.right) | |
| def BST_inorder(bst): | |
| BST_inorder_node(bst.root) | |
| def BST_preorder_node(node): | |
| if node: | |
| print(node.value) | |
| BST_preorder_node(node.left) | |
| BST_preorder_node(node.right) | |
| def BST_preorder(bst): | |
| BST_preorder_node(bst.root) | |
| def BST_posorder_node(node): | |
| if node: | |
| BST_posorder_node(node.left) | |
| BST_posorder_node(node.right) | |
| print(node.value) | |
| def BST_preorder(bst): | |
| BST_posorder_node(bst.root) | |
| def BST_search_rec_node(node, value): | |
| if node == None: | |
| return False | |
| elif node.value == value: | |
| return True | |
| elif value < node.value: | |
| return BST_search_rec_node(node.left, value) | |
| else: | |
| return BST_search_rec_node(node.right, value) | |
| def BST_search_rec(bst, value): | |
| return BST_search_rec_node(bst.root, value) | |
| def BST_invert_rec_node(node): | |
| if node: | |
| node.left, node.right = node.right, node.left | |
| BST_invert_rec_node(node.left) | |
| BST_invert_rec_node(node.right) | |
| def BST_invert_rec(bst): | |
| BST_invert_rec_node(bst.root) | |
| bst = BinarySearchTree() | |
| node1 = TreeNode(10, None, None) | |
| node2 = TreeNode(8, None, None) | |
| node3 = TreeNode(12, None, None) | |
| BST_insert(bst, node1) | |
| BST_insert(bst, node2) | |
| BST_insert(bst, node3) | |
| BST_inorder(bst) | |
| print() | |
| print("Search for 10: {}".format(BST_search_rec(bst, 10))) | |
| print("Search for 20: {}".format(BST_search_rec(bst, 20))) | |
| print() | |
| bst = BinarySearchTree() | |
| node1 = TreeNode(10, None, None) | |
| node2 = TreeNode(8, None, None) | |
| node3 = TreeNode(12, None, None) | |
| node4 = TreeNode(9, None, None) | |
| node5 = TreeNode(11, None, None) | |
| BST_insert_rec(bst, node1) | |
| BST_insert_rec(bst, node2) | |
| BST_insert_rec(bst, node3) | |
| BST_insert_rec(bst, node4) | |
| BST_insert_rec(bst, node5) | |
| BST_inorder(bst) | |
| print() | |
| # Warning: the tree is not BST | |
| # anymore after inversion!! | |
| BST_invert_rec(bst) | |
| BST_inorder(bst) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment