test code:
10.1 Binary Search Tree In this assignment, you will implement a Binary Search Tree. You will also need to implement a Node class. This class will not be tested, but is needed to implement the BST. Your BST must implement the following methods. You are free to implement additional helper methods. It is recommended you create your own helper methods. Constructor: Creates an Empty Tree String Method: Returns the string "Empty Tree" for an empty tree. Otherwise, returns a string with the tree in Preorder, Inorder, and Postorder. When printing a Empty/Null node print out the letter N. Put a single space after each value. This means your lines will end with a single extra space. Insert: Insert value x into the tree. Insert ignores duplicated values. Do not insert doubles. find: Returns true/false if value x is in the tree. A testbed is provided that will test features of your code. Remember, you can add your own helper methods. Test Bed for Binary Search Tree Class Enter Test Number (1-6): Make a Balanced Tree. Inserting: [6, 8, 4, 3, 7, 5, 9] Your Tree looks like: Preorder: 6 4 3 NN 5 NN 8 7 NN 9 NN Inorder: N 3 N 4 N 5 N 6 N 7 N8N9N Postorder: NN 3 N N 5 4 NN 7 NN 9 8 6 LAB ACTIVITY 10.1.1: Binary Search Tree 101.1 Dinor ser 0/100 Current file: bst.py Load default template... 1 #Complete this class definition BEBOU 3 #It is recommended you create a node class and additional methods 4 class BST: def _init__(self): return def _str_(self): return def insert(self,x): return def find(self,x): return 4 from bst import * 9 10 16 18 20 21 24 26 29 32 34 3 39 6 print("Test Bed for Binary Search Tree Class") 7 x = int(input("Enter Test Number (1-6): ")) 8 if x==1: print("Make an Empty Tree") T = BST 11 print("Your Tree looks like:") 12 print(T) 13 if x==2: print("Make a Balanced Tree.") 15 balance=[6, 8, 4, 3, 7, 5, 9] print("Inserting:", balance) T = BST() for x in balance: T.insert(x) print("Your Tree looks like:") print(T) 22 if x==3: print("Make a Left Heavy Tree.") left=[8,7,6,5,4,3,2] print("Inserting:", left) T = BST() for x in left: 28 T.insert(x) print("Your Tree looks like:") 30 print(1) 31 if x==4: print("Make a Right Heavy Tree.") right=[1,2,3,4,6,5,7] print("Inserting:",right) T = BST 36 for x in right: 37 T.insert(x) 38 print("Your Tree looks like:") print(T) 40 if x==5: 41 print("Make a Random Tree") 42 import random random.seed (91) rand = [random.randint(0,100) for x in range(0,15)] print("Inserting:",rand) 46 T = BST for x in rand: T.insert(x) 49 print("Your Tree looks like:") print(T) 51 if x==6: print("Testing Find") import random random. seed (26) rand = [random.randint(0,20) for x in range(0,15)] print("Inserting:",rand) T = BST() for x in rand: T.insert(x) print("Your Tree looks like:") print(T) print("Test all Integers from 0 to 20") tests=0 passed=0 for x in range (0,21): correct = x in rand student = T.find(x) if correct == student: passed+=1 else: print("Searched for",x) print("Expected", correct) print("Find Returned", student) tests+=1 print("Passed", passed, "out of", tests) 43 45 > 53 57 58 60 62 66 6> 70 74 75 76
