Below is a python program I am writing that makes a tree and then has the abilit

Question

 Below is a python program I am writing that makes a tree and then has the ability to delete a node from the tree. The part that makes the tree works fine, but the part that deletes the node does not. Can someone help me with the portion that deletes a node.   class Node:     def __init__(self, data, left=None, right=None):         self.data = data         self.left = left         self.right = right      def __str__(self):         return str(self.data)   class Tree:     def __init__(self, root=None):         self.root = root      def __str__(self):         # Create a 2D that represents the tree         i = 0         nodes = [[self.root]]         string = [[str(self.root)]]         if self.root.left is not None or self.root.right is not None:             more_branches = True         else:             more_branches = False         while more_branches:             more_branches = False             nodes.append([])             string.append([])             for node in nodes[i]:                 if node is not None:                     nodes[i+1].append(node.left)                     nodes[i+1].append(node.right)                     string[i+1].append(str(node.left))                     string[i+1].append(str(node.right))                     if node.left is not None or node.right is not None:                         more_branches = True                 else:                     nodes[i+1].append(None)                     nodes[i+1].append(None)                     string[i+1].append(str(None))                     string[i+1].append(str(None))              if more_branches:                 i += 1         del nodes[i+1]         del string[i+1]          # Format the 2D array into a string         max_entry_size = 0         for i in range(len(string)):             for j in range(len(string[i])):                 if string[i][j] == 'None':                     string[i][j] = ""                 if len(string[i][j]) > max_entry_size:                     max_entry_size = len(string[i][j])         s = ""         num_rows = len(string)         for i in range(num_rows):             left_margin = (2**(num_rows-i-1)-1)*max_entry_size             spacing = (2**(num_rows-i)-1)*max_entry_size             s += left_margin*" "             for j in range(len(string[i])):                 l = len(string[i][j])                 s += int(round((max_entry_size - l)/2))*" " + string[i][j] +                       (max_entry_size - l - int(round((max_entry_size - l)/2)))*" " + spacing*" "             s += " "         return s      def insert(self, x):         def ins(current_node, x):             if current_node.left is not None and current_node.data > x:                 ins(current_node.left, x)             if current_node.right is not None and current_node.data < x:                 ins(current_node.right, x)             if current_node.left is None and current_node.data > x:                 current_node.left = Node(x)             elif current_node.right is None and current_node.data <= x:                 current_node.right = Node(x)         if self.root is None:             self.root = Node(x)         else:             ins(self.root, x)      def remove(self, data):         if self.root and self.root.data == data:  # special case for removing the root             self.root = self.root.delete()             return         else:  # general case, removing a child node of some parent             parent = self.root             while parent:                 if data < parent.data:                     child = parent.left                     if child and child.data == data:                         parent.left = child.delete()                         return                     parent = child                 else:                     child = parent.right                     if child and child.data == data:                         parent.right = child.delete()                         return                     parent = child   x = Tree()  x.insert(23) x.insert(15) x.insert(37) x.insert(6) x.insert(1) x.insert(17) x.insert(35) x.insert(4) x.insert(9) x.insert(14) x.insert(15) x.insert(18) x.remove(18)   print(x) 

Explanation / Answer

def delete(self, key): """ delete the node with the given key and return the root node of the tree """ if self.key == key: # found the node we need to delete if self.right and self.left: # get the successor node and its parent [psucc, succ] = self.right._findMin(self) # splice out the successor # (we need the parent to do this) if psucc.left == succ: psucc.left = succ.right else: psucc.right = succ.right # reset the left and right children of the successor succ.left = self.left succ.right = self.right return succ else: # "easier" case if self.left: return self.left # promote the left subtree else: return self.right # promote the right subtree else: if self.key > key: # key should be in the left subtree if self.left: self.left = self.left.delete(key) # else the key is not in the tree else: # key should be in the right subtree if self.right: self.right = self.right.delete(key) return self def _findMin(self, parent): """ return the minimum node in the current tree and its parent """ # we use an ugly trick: the parent node is passed in as an argument # so that eventually when the leftmost child is reached, the # call can return both the parent to the successor and the successor if self.left: return self.left._findMin(self) else: return [parent, self] Above is a code to delete a node of tree in python.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.