PYTHON:
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 missing traversal, but not its order. Please help me fix it or you may create your own program with the same output as the image below. Thank you.
# Main program
inorder_list = []
preorder_list = []
postorder_list = []
n = int(input("How many nodes want to enter? "))
# Methods
def search(arr, x, n):
for i in range(n):
if (arr[i] == x):
return i
return -1
def PostOrderT(Ino, preo, n):
root = search(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)
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 4 steps with 4 images
