Input insert 20 insert 10 insert 30 insert 15 insert 25 insert 35 insert 5 preorder inorder search 20 search 10 postorder inorder exit Expected Output 20 is inserted 10 is inserted 30 is inserted 15 is inserted 25 is inserted 35 is inserted 5 is inserted 5 35 25 15 10 20 30 5 10 15 20 25 30 35 20 is found! 10 is found! 5 15 30 25 35 20 10 5 10 15 20 25 30 35 But when I run my code, I get this output: 20 is inserted 10 is inserted 30 is inserted 15 is inserted 25 is inserted 35 is inserted 5 is inserted 5 35 25 10 15 20 30 5 10 15 20 25 30 35 20 is found! 10 is found! 5 15 30 35 25 20 10 5 10 15 20 25 30 35 So the problem only appears in the preorder output. Below is my full Python code. Can you please check what’s wrong with it? class Node: def __init__(self, key): self.key = key self.left = None self.right = None self.parent = None class BST: def __init__(self): self.root = None def search(self, key): v = self.root while v: if key == v.key: return v elif key < v.key: v = v.left else: v = v.right return None def insert(self, key): v = self.root p = None while v: p = v if key < v.key: v = v.left else: v = v.right new_node = Node(key) new_node.parent = p if p is None: self.root = new_node elif key < p.key: p.left = new_node else: p.right = new_node return new_node def preorder(self, v): if v: print(v.key, end=" ") self.preorder(v.left) self.preorder(v.right) def inorder(self, v): if v: self.inorder(v.left) print(v.key, end=" ") self.inorder(v.right) def postorder(self, v): if v: self.postorder(v.left) self.postorder(v.right) print(v.key, end=" ") class SplayTree(BST): def rotateRight(self, x): y = x.left if y: x.left = y.right if y.right: y.right.parent = x y.parent = x.parent if x.parent is None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y if y: y.right = x x.parent = y def rotateLeft(self, x): y = x.right if y: x.right = y.left if y.left: y.left.parent = x y.parent = x.parent if x.parent is None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y if y: y.left = x x.parent = y def splay(self, x): while x.parent: p = x.parent gp = p.parent if gp is None: if x == p.left: self.rotateRight(p) else: self.rotateLeft(p) elif x == p.left and p == gp.left: self.rotateRight(gp) self.rotateRight(p) elif x == p.right and p == gp.right: self.rotateLeft(gp) self.rotateLeft(p) elif x == p.right and p == gp.left: self.rotateLeft(p) self.rotateRight(gp) else: self.rotateRight(p) self.rotateLeft(gp) return x def pred(self, key): v = self.root pred = None while v: if key > v.key: pred = v v = v.right else: v = v.left return pred def succ(self, key): v = self.root succ = None while v: if key < v.key: succ = v v = v.left else: v = v.right return succ def search(self, key): v = super().search(key) if v: self.root = self.splay(v) return v else: w = self.pred(key) if not w: w = self.succ(key) if w: self.root = self.splay(w) return None def insert(self, key): v = super().insert(key) self.root = self.splay(v) return v def delete(self, x): if not x: return self.root = self.splay(x) L = self.root.left R = self.root.right if L: L.parent = None m = L while m.right: m = m.right self.root = self.splay(m) self.root.right = R if R: R.parent = self.root else: self.root = R if R: R.parent = None T = SplayTree() while True: cmd = input().split() if cmd[0] == 'insert': v = T.insert(int(cmd[1])) print("+ {0} is inserted".format(v.key)) elif cmd[0] == 'delete': v = T.search(int(cmd[1])) T.delete(v) print("- {0} is deleted".format(int(cmd[1]))) elif cmd[0] == 'search': v = T.search(int(cmd[1])) if v == None: print("* {0} is not found!".format(cmd[1])) else: print("* {0} is found!".format(cmd[1])) elif cmd[0] == 'preorder': T.preorder(T.root) print() elif cmd[0] == 'postorder': T.postorder(T.root) print() elif cmd[0] == 'inorder': T.inorder(T.root) print() elif cmd[0] == 'exit': break else: print("* not allowed command. enter a proper command!") Continue reading...
