PYTHON: Please help me fix my code. It was supposed to ask the user to input an inorder traversal and let them choose whether to enter postorder or preorder, then identify the order of the missing traversal, just like the image below. However, my code can only identify the POSTORDER traversal but not the PREORDER. There is something wrong with my def function on def PreOrderT(). Please help me fix it. Thank you. # Main program inorder_list = [] preorder_list = [] postorder_list = [] n = int(input("How many nodes want to enter? ")) # Methods def searchR(arr, x, n): # CHANGED THE NAME OF FUNCTION AS THERE ARE TWO FUNCTION WITH SAME NAME for i in range(n): if (arr[i] == x): return i return -1 def PostOrderT(Ino, preo, n): root = searchR(Ino, preo[0], n) if (root != 0): PostOrderT(Ino, preo[1:n], root) if (root != n - 1): PostOrderT(Ino[root + 1:n], preo[root + 1:n], n - root - 1) print(preo[0], end=" ") # Make new node class newNode: def __init__(self, data): self.data = data self.left = self.right = None # Construct binary tree def MakeTree(Ino, posto, inoStrt, inoEnd, p_Index): if (inoStrt > inoEnd): return None node = newNode(posto[p_Index[0]]) p_Index[0] -= 1 if (inoStrt == inoEnd): return node iIndex = search(Ino, inoStrt, inoEnd, node.data) node.right = MakeTree(Ino, posto, iIndex + 1, inoEnd, p_Index) node.left = MakeTree(Ino, posto, inoStrt, iIndex - 1, p_Index) return node def bTree(Ino, posto, n): p_Index = [n - 1] return MakeTree(Ino, posto, 0, n - 1, p_Index) def search(arr, astrt, aend, value): i = 0 for i in range(astrt, aend + 1): if (arr[i] == value): break return i def PreOrderT(node): if node == None: return print(node.data, end=" ") PreOrderT(node.left) PreOrderT(node.right) print("Enter INORDER:") for i in range(0, n): ele = input().split() if len(ele) == n: for i in ele: inorder_list.append(i) # adding the element break elif len(ele) > n: print("You have entered more nodes") break else: print("You have entered less nodes") break print(inorder_list) print("\nWould you like to use Preorder or Postorder?") choice = int(input("Press [1] for PREORDER and Press [2] for POSTORDER>> ")) if choice == 1: print("Enter PREORDER: ") for i in range(0, n): ele = input().split() if len(ele) == n: for i in ele: preorder_list.append(i) # adding the element break elif len(ele) > n: print("You have entered more nodes") break else: print("You have entered less nodes") break print(preorder_list) print("\nMissing Traversal Identified!") print("POSTORDER traversal: ") bTree(inorder_list, preorder_list, n) # NEED TO BUILD THE TREE FIRST PostOrderT(inorder_list, preorder_list, n) # CALLING CORRECT FUNCTION elif choice == 2: print("Enter POSTORDER: ") for i in range(0, n): ele = input().split() if len(ele) == n: for i in ele: postorder_list.append(i) # adding the element break elif len(ele) > n: print("You have entered more nodes") break else: print("You have entered less nodes") break print(postorder_list) print("\nMissing Traversal Identified!") print("PREORDER traversal: ") PostOrderT(inorder_list, preorder_list, n) else: print("Invalid choice")
PYTHON:
Please help me fix my code. It was supposed to ask the user to input an inorder traversal and let them choose whether to enter postorder or preorder, then identify the order of the missing traversal, just like the image below. However, my code can only identify the POSTORDER traversal but not the PREORDER. There is something wrong with my def function on def PreOrderT(). Please help me fix it. Thank you.
# Main program
inorder_list = []
preorder_list = []
postorder_list = []
n = int(input("How many nodes want to enter? "))
# Methods
def searchR(arr, x, n): # CHANGED THE NAME OF FUNCTION AS THERE ARE TWO FUNCTION WITH SAME NAME
for i in range(n):
if (arr[i] == x):
return i
return -1
def PostOrderT(Ino, preo, n):
root = searchR(Ino, preo[0], n)
if (root != 0):
PostOrderT(Ino, preo[1:n], root)
if (root != n - 1):
PostOrderT(Ino[root + 1:n], preo[root + 1:n], n - root - 1)
print(preo[0], end=" ")
# Make new node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Construct binary tree
def MakeTree(Ino, posto, inoStrt, inoEnd, p_Index):
if (inoStrt > inoEnd):
return None
node = newNode(posto[p_Index[0]])
p_Index[0] -= 1
if (inoStrt == inoEnd):
return node
iIndex = search(Ino, inoStrt, inoEnd, node.data)
node.right = MakeTree(Ino, posto, iIndex + 1, inoEnd, p_Index)
node.left = MakeTree(Ino, posto, inoStrt, iIndex - 1, p_Index)
return node
def bTree(Ino, posto, n):
p_Index = [n - 1]
return MakeTree(Ino, posto, 0, n - 1, p_Index)
def search(arr, astrt, aend, value):
i = 0
for i in range(astrt, aend + 1):
if (arr[i] == value):
break
return i
def PreOrderT(node):
if node == None:
return
print(node.data, end=" ")
PreOrderT(node.left)
PreOrderT(node.right)
print("Enter INORDER:")
for i in range(0, n):
ele = input().split()
if len(ele) == n:
for i in ele:
inorder_list.append(i) # adding the element
break
elif len(ele) > n:
print("You have entered more nodes")
break
else:
print("You have entered less nodes")
break
print(inorder_list)
print("\nWould you like to use Preorder or Postorder?")
choice = int(input("Press [1] for PREORDER and Press [2] for POSTORDER>> "))
if choice == 1:
print("Enter PREORDER: ")
for i in range(0, n):
ele = input().split()
if len(ele) == n:
for i in ele:
preorder_list.append(i) # adding the element
break
elif len(ele) > n:
print("You have entered more nodes")
break
else:
print("You have entered less nodes")
break
print(preorder_list)
print("\nMissing Traversal Identified!")
print("POSTORDER traversal: ")
bTree(inorder_list, preorder_list, n) # NEED TO BUILD THE TREE FIRST
PostOrderT(inorder_list, preorder_list, n) # CALLING CORRECT FUNCTION
elif choice == 2:
print("Enter POSTORDER: ")
for i in range(0, n):
ele = input().split()
if len(ele) == n:
for i in ele:
postorder_list.append(i) # adding the element
break
elif len(ele) > n:
print("You have entered more nodes")
break
else:
print("You have entered less nodes")
break
print(postorder_list)
print("\nMissing Traversal Identified!")
print("PREORDER traversal: ")
PostOrderT(inorder_list, preorder_list, n)
else:
print("Invalid choice")
Step by step
Solved in 3 steps with 1 images
