Topic: Binary Search Tree
INSTRUCTIONS
Below is code for a Binary Search Tree Class. 7 of the methodsin this implementation are incomplete (vacuous): find, size,preorder, inorder, postorder, __str__ and height. Please completethem. Use the testing code to test and confirm yourimplementation.
#Finding the height of a binary tree
method
points
find
2
size
1
inorder
2
preorder
1
postorder
1
str
2
height
1
ABOUT THE CLASSES
The Node class describes the structure of a node in the tree:each node has a data item and can have a left and right child.
The BinarySearchTree class is responsible for tree-level methodssuch as buildBST, inserting a data value in the right place/node inthe BST tree (we populate the tree given a list data values throughmain), and the tree traversal methods.
# -*- coding: utf-8 -*-
"""
Binary Search Tree
Plus tree traversal methods
NOTE: return statements were placed immediately after thefunction declarations so you can run the code and see the printstatements before beginning the task.
HOWEVER ... You will need to move the return statements to theend of the functions once you complete each functionimplementation.
"""
import matplotlib.pyplot as plt
import networkx as nx
class Node:
def __init__(self, data): #Constructor of Node class
# A node has a data value, a left child node and a rightchild node
self.data = data #dataitem
self.left = None #leftchild, initially empty
self.right = None #rightchild, initially empty
def __str__(self): # Printing anode
return str(self.data) #returnas string
#===================================================================
#===================================================================
class BinarySearchTree:
def __init__(self): # Constructorof BinarySearchTree class
self.root = None #Initially, an empty root node
#===================================================================
def buildBST(self, val): # Build("create") a binary search tree
if self.root == None:
self.root = Node(val)
else:
current = self.root
while 1:
if val < current.data:
if current.left:
current = current.left #Go left...
else:
current.left = Node(val) #Left child is empty; place value here
break;
elif val > current.data:
if current.right:
current = current.right #Go right...
else:
current.right = Node(val) #Right child is empty; place value here
break;
else:
break
#===================================================================
def find(self,target): return # Find a node withthe 'target' value in the BST
'''
returns true if found, false otherwise
'''
## TODO: Complete this method! ##
#===================================================================
def size(self,node): return # Counts the number ofnodes in the BST
'''
returns number of nodes
'''
## TODO: Complete this method! ##
#===================================================================
def inorder(self,node): return # Performing in-ordertree traversal
'''
prints values as encountered inorder
'''
## TODO: Complete this method! ##
#===================================================================
def preorder(self,node): return # Performing pre-ordertree traversal
'''
prints values as encountered preorder
'''
## TODO: Complete this method! ##
#===================================================================
def postorder(self,node): return # Performingpost-order tree traversal
'''
prints values as encountered postorder
'''
## TODO: Complete this method! ##
#===================================================================
def __str__(self): return "SeeGraph Diagram in Figure\n"
'''
Builds networkx visualization of the BST
The purpose of this method is to render a visualization of aconstructed BST Tree to confirm correctness.
Hint: To complete this you will need to create a node list, edgelist, and/or an adjacency matrix. You can then easily construct agraph visualization using networkx.
Slightly alter one of your traversal methods (or the buildBSTmethod)
above so that the appropriate structure(s) is constructed andsaved as an attribute(s) to the BST class, eg, edgeList.
Hint: Use a directed graph (DiGraph) so you can more easily
identify the root, leaf, and internal nodes. The standardnetworkx method draw will suffice. It will render the tree as astandard graph (ie no clear root), but you can determine which nodeis the root if you use a DiGraph. Once the graph is constructed, aplot is created.
'''
# See docs here to helphttps://networkx.org/documentation/stable/tutorial.html
# Insert Code to display figure here
#===================================================================
def height(self,node): return # Performingpost-order tree traversal
'''
prints tree height
'''
## TODO: Complete this method! ##
#===================================================================
##################
## Testing Code ##
##################
tree = BinarySearchTree()
treeEmpty = BinarySearchTree() #Empty tree
arr = [8,3,1,6,4,7,10,14,13] #Array of nodes (data items)
for i in arr: #For each data item, build the Binary Search Tree
tree.buildBST(i)
print('What\'s the size of the tree?')
print(tree.size(tree.root)) #size method
print('What\'s the size of the tree?')
print(treeEmpty.size(treeEmpty.root))
print("")
print ('In-order Tree Traversal:')
tree.inorder(tree.root) #Perform in-order tree traversal, and print
print("")
print ('Pre-order Tree Traversal:')
tree.preorder(tree.root) #Perform pre-order tree traversal, and print
print("")
print ('Post-order Tree Traversal:')
tree.postorder(tree.root) #Perform post-order tree traversal, and print
print("")
print ('Find 7:', end=" ") # findmethod
print(tree.find(7))
print('Find 5:', end=" ")
print(tree.find(5))
print('Find 30:', end=" ")
print(tree.find(30))
print("")
print("")
print ('Display Figure of Tree:')
print(tree)
print("")
print('Height of the Tree:')
print(tree.height(tree.root))
#The following are the same as above, just to showyou proper indentation:
- Please Use Python To Complete The Following Within 2 Hours Please Have Your Own Answer Not Just Copy From Somewhere P 1 (19.25 KiB) Viewed 29 times
- Please Use Python To Complete The Following Within 2 Hours Please Have Your Own Answer Not Just Copy From Somewhere P 2 (17.17 KiB) Viewed 29 times
- Please Use Python To Complete The Following Within 2 Hours Please Have Your Own Answer Not Just Copy From Somewhere P 3 (40.07 KiB) Viewed 29 times
def buildBST (self, val): # Build ("create") a binary search tree if self.root == None: self.root Node (val) else: current = self.root while 1: if val< current.data: if current.left: current current.left # Go Left... else: current.left = break; elif val > current.data: else: if current.right: current = current.right # Go right... else: ====== Node(val) # Left child is empty; place value here break current.right = Node(val) # Right child is empty; place value here break;
# # # def find(self, target): return # Find a node with the 'target' value in the BST returns true if found, false otherwise III ## TODO: Complete this method! ## === def size (self, node): return # Counts the number of nodes in the BST returns number of nodes ## TODO: Complete this method! ## ======== def inorder (self, node): return # Performing in-order tree traversal prints values as encountered inorder ## TODO: Complete this method! ## === def preorder (self, node): return # Performing pre-order tree traversal prints values as encountered preorder ## TODO: Complete this method! ## ==== def postorder (self, node): return # Performing post-order tree traversal prints values as encountered postorder ## TODO: Complete this method! ##
# def _str_(self): return "See Graph Diagram in Figure\n" TIE Builds networkx visualization of the BST === The purpose of this method is to render a visualization of a constructed BST Tree to confirm correctness. Hint: To complete this you will need to create a node list, edge list, and/or an adjacency matrix. You can then easily construct a graph visualization using networkx. slightly alter one of your traversal methods (or the buildBST method) above so that the appropriate structure(s) is constructed and saved as an attribute(s) to the BST class, eg, edgeList. Hint: Use a directed graph (DiGraph) so you can more easily identify the root, leaf, and internal nodes. The standard networkx method draw will suffice. It will render the tree as a standard graph (ie no clear root), but you can determine which node is the root if you use a DiGraph. Once the graph is constructed, a plot is created. # Revisit previous exercises and examples using Networkx to help! # See docs here to help https://networkx.org/documentation/stable/tutorial.html # Insert Code to diplay figure here === def height (self, node): return # Performing post-order tree traversal prints tree height ## TODO: Complete this method! ## =====
################## ## Testing Code ## ################## tree = BinarySearch Tree() treeEmpty = BinarySearchTree() arr = [8,3,1,6,4,7,10,14,13] for i in arr: tree.buildBST (1) print('What\'s the size of the tree?') print (tree.size(tree.root)) print('What\'s the size of the tree?') print (treeEmpty.size(treeEmpty.root)) print("") print ('In-order Tree Traversal: ') tree.inorder (tree.root) # Empty tree # Array of nodes (data items) # For each data item, build the Binary Search Tree print("") print ('Find 7:', end=" ") print (tree.find(7)) print("") print ('Pre-order Tree Traversal:') tree.preorder (tree.root) print('Find 5:', end=" ") print (tree.find(5)) # size method print('Find 30:', end=" ") print (tree.find(30)) print("") print ('Post-order Tree Traversal: ') tree.postorder (tree.root) print("") print("") # Perform in-order tree traversal, and print print("") print('Height of the Tree: ') print (tree.height(tree.root)) # Perform pre-order tree traversal, and print # Perform post-order tree traversal, and print # find method print ('Display Figure of Tree:') print (tree)
What's the size of the tree? None What's the size of the tree? None In-order Tree Traversal: Pre-order Tree Traversal: Post-order Tree Traversal: Find 7: None Find 5: None Find 30: None Display Figure of Tree: See Graph Diagram in Figure