So I am trying to create a binary tree within python using classes but I have gotten stuck on this last bit.
When this happens, it is meant to find the in-order successor, replace the targeted node with it's contents and then either delete the node if it doesn't have any children or replace the node with it's children if they exist.
It can do the no children deletion but it seems to struggle on the other one.
For example, in the following binary tree, if I wanted to delete node '50', then it is meant to to be replaced by '54' and '56' should replace node '54':
However, this does not work.
Here's the rest of my code:
Thanks!
def deleteNode(self, node, data): if self.searchNode(node, data) is None: print("Node doesn't exist") return None else: # Node exists if data < node.data: node.left = self.deleteNode(node.left, data) elif data > node.data: node.right = self.deleteNode(node.right, data) elif data == node.data: # Node has no children if node.left is None and node.right is None: del node return None # Node has 1 child elif node.left is None: temp = node.right node = None return temp elif node.right is None: temp = node.left node = None return temp else: # Node has 2 children so find inorder successor temp = self.inorderSuccessor(node.right) node.data = temp.dataThis code is meant to remove an element and replace it within it's child. Which is does perfectly fine up until the node has 2 children.
When this happens, it is meant to find the in-order successor, replace the targeted node with it's contents and then either delete the node if it doesn't have any children or replace the node with it's children if they exist.
It can do the no children deletion but it seems to struggle on the other one.
For example, in the following binary tree, if I wanted to delete node '50', then it is meant to to be replaced by '54' and '56' should replace node '54':
However, this does not work.
Here's the rest of my code:
import random randomList = [] randomListSize = 10 resultList = [] class Node: def __init__(self, value): self.data = value self.left = None self.right = None class Tree: def createNode(self, data): return Node(data) def insertNode(self, node, data): if node is None: # Create root node return self.createNode(data) # Root node already exists if data < node.data: # New node data is less than root node node.left = self.insertNode(node.left, data) elif data > node.data: # New node data is bigger than root node node.right = self.insertNode(node.right, data) # Save new node data return node def searchNode(self, node, data): if node is None or node.data == data: # Node is found return node elif node.data > data: # Node may be to the left of the root return self.searchNode(node.left, data) elif node.data < data: # Node may be to the right of the root return self.searchNode(node.right, data) else: # Node is not found return None def deleteNode(self, node, data): if self.searchNode(node, data) is None: print("Node doesn't exist") return None else: # Node exists if data < node.data: node.left = self.deleteNode(node.left, data) elif data > node.data: node.right = self.deleteNode(node.right, data) elif data == node.data: # Node has no children if node.left is None and node.right is None: del node return None # Node has 1 child elif node.left is None: temp = node.right node = None return temp elif node.right is None: temp = node.left node = None return temp else: # Node has 2 children so find inorder successor temp = self.inorderSuccessor(node.right) node.data = temp.data def inorderSuccessor(self, node): while node.left is not None: node = node.left return node def preorder(self, node): # Root then left sub-tree then right sub-tree if node is not None: print(node.data) self.preorder(node.left) self.preorder(node.right) def inorder(self, node): # Left sub-tree then root then right sub-tree if node is not None: self.inorder(node.left) print(node.data) self.inorder(node.right) def postorder(self, node): # Left sub-tree then right sub-tree then root if node is not None: self.postorder(node.left) self.postorder(node.right) print(node.data) def setup(): randomList = [] for i in range(randomListSize): randomList.append(random.randint(1, 100)) print(randomList) randomList = [59, 90, 93, 23, 60, 85, 64, 23, 15, 15] print(randomList) tree = Tree() root = tree.insertNode(None, randomList[0]) # Create root node for i in range(len(randomList) - 1): tree.insertNode(root, randomList[i + 1]) # Create each child node return tree, root def traverse(): while True: try: user = int(input("1 for preorder, 2 for inorder and 3 for postorder: ")) if user == 1: tree.preorder(root) elif user == 2: tree.inorder(root) elif user == 3: tree.postorder(root) else: print("Invalid choice") except ValueError: print("Invalid choice") break if __name__ == "__main__": tree, root = setup() while True: try: userChoice = int( input("Enter 1 to add a node, 2 to search for a node, 3 to delete a node and 4 to traverse the tree: ")) if userChoice == 1: newNode = int(input("Enter a number: ")) tree.insertNode(root, newNode) elif userChoice == 2: userSearch = int(input("Enter a number: ")) if tree.searchNode(root, userSearch) is not None: print(userSearch, "exists") else: print("Node doesn't exist") elif userChoice == 3: removeNode = int(input("Enter a number: ")) tree.deleteNode(root, removeNode) elif userChoice == 4: traverse() else: print("Invalid choice") except ValueError: print("Invalid choice")If anyone has any ideas on how to fix this, it'll be greatly appreciated. If anyone has any ideas on how to improve my code, that'll be appreciated too.
Thanks!