Python Intro. BST Project ( Python 3 ). Implimenting Binary Search Tree (BST). I
ID: 3912155 • Letter: P
Question
Python Intro. BST Project ( Python 3 ). Implimenting Binary Search Tree (BST). In this program, we try to implement a BST and there are tests on the bottom that we using to test the code. And I am stuck with add, Inorder, postorder, preorder, BFS. can somebody please help me out with this project, thak you so much.
The project is here: [ https://jpst.it/1iBAj ] < < Click this for full project outline.
Some one provided this answer below earlier and I couldnt figure out how to implement code below into my project :
//Adding a node in BST
//if key is given,first make a new node with given key then call add fuction
def add(root,node):
if root is None:
root = node
else:
if root.val < node.val:
if root.right is None:
root.right = node
else:
add(root.right, node)
else:
if root.left is None:
root.left = node
else:
add(root.left, node)
//Preorder Traversal using Recursion
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
//Inorder traversal using Recursion
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
//Postorder traversal using Recursion
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val)
//BFS(Breadth First Seach) in BST
//fuction to print BFS by printing node level by level
def printBFS(root):
h = height(root)
for i in range(1, h+1):
printCurrentLevel(root, i)
//function to print the nodes at level(as given in parameter of function)
def printCurrentLevel(root , level):
if root is None:
return
if level == 1:
print "%d" %(root.val),
elif level > 1 :
printCurrentLevel(root.left , level-1)
printCurrentLevel(root.right , level-1)
//function to determine no of levels tree have
def height(node):
if node is None:
return 0
else :
lheight = height(node.left) //height of Left subtree
rheight = height(node.right) //height of Right subtree
if lheight > rheight :
return lheight+1
else:
return rheight+1
Explanation / Answer
for that part to be integrated in your code, you need to add some more code.
# Begin of bst.py
class BST:
def add(self, root, node):
if root is None:
root = node
else:
if root.val < node.val:
if root.right is None:
root.right = node
else:
self.add(root.right, node)
else:
if root.left is None:
root.left = node
else:
self.add(root.left, node)
# Preorder Traversal using Recursion
def preorder(self, root):
if root:
print(root.val)
self.preorder(root.left)
self.preorder(root.right)
# Inorder traversal using Recursion
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.val)
self.inorder(root.right)
# Postorder traversal using Recursion
def postorder(self, root):
if root:
self.postorder(root.left)
self.postorder(root.right)
print(root.val)
# BFS(Breadth First Seach) in BST
# fuction to print BFS by printing node level by level
def printBFS(self, root):
h = self.height(root)
for i in range(1, h+1):
self.printCurrentLevel(root, i)
# function to print the nodes at level(as given in parameter of function)
def printCurrentLevel(self, root, level):
if root is None:
return
if level == 1:
print "%d" % (root.val),
elif level > 1:
self.printCurrentLevel(root.left, level-1)
self.printCurrentLevel(root.right, level-1)
# function to determine no of levels tree have
def height(self, node):
if node is None:
return 0
else:
lheight = self.height(node.left) # height of Left subtree
rheight = self.height(node.right) # height of Right subtree
if lheight > rheight:
return lheight+1
else:
return rheight+1
# End of bst.py
# BEGIN of node.py
# A node class to pass node to bst
class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
# END of node.py
# BEGIN of test.py
from bst import BST
from node import Node
# initializing a root node
root = Node(10)
# initializing bst
my_bst = BST()
# adding root to tree
my_bst.add(None, root)
# adding some other nodes to root
my_bst.add(root, Node(2))
my_bst.add(root, Node(5))
my_bst.add(root, Node(7))
my_bst.add(root, Node(8))
my_bst.add(root, Node(3))
my_bst.add(root, Node(4))
my_bst.add(root, Node(9))
my_bst.inorder(root)
my_bst.printBFS(root)
# END of test.py
make sure all three files are in same directory or else you can write everythin in one file, but I think modularity is important.
Hope you can understand easily, feel free to ask doubts
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.