Below is a program I am writing that makes a tree and then has the ability to de
ID: 3829998 • Letter: B
Question
Below is a 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
public boolean remove(int value, BSTNode parent) {
if (value < this.value) {
if (left != null)
return left.remove(value, this);
else
return false;
} else if (value > this.value) {
if (right != null)
return right.remove(value, this);
else
return false;
} else {
if (left != null && right != null) {
this.value = right.minValue();
right.remove(this.value, this);
} else if (parent.left == this) {
parent.left = (left != null) ? left : right;
} else if (parent.right == this) {
parent.right = (left != null) ? left : right;
}
return true;
}
}
public int minValue() {
if (left == null)
return value;
else
return left.minValue();
}
Above is a code to delete a node from tree.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.