I am having a bit of a hard time with a recursive insert function that I been studying through zybooks data structures.I didn't have any issues with a normal insert but with the recursive it is confusing me a lot. The function is gathering the tree information as a parameter. The keys are the names which are all unique. I haven't inserted anything in the parameter to put in the function in the else statement. Would appreciate some pointers if possible.
class Star:
def __init__(self, hvg_db, name, mag, spectral, habit, dist):
self.hvg_db = hvg_db
self.display_name = name #
self.magnitude = mag
self.spectral_class = spectral
self.habitable = habit #
self.distance_parsecs = dist
class TreeNode:
def __init__(self, star):
self.left = None
self.right = None
self.star_info = star
self.name = "N" + str(self.star_info.hvg_db)
self.key = star.display_name
class Tree:
def __init__(self, name):
self.name = name
self.node_num = 0
self.node_list = []
self.root = None
def insert_rec(self, star): # method receives star info (star, magnitude, habitable, etc
star = TreeNode(star)
if self.root is None:
self.root = star
print("Parent Activated")
parent = self.root
if star.key < parent.key:
if parent.left is None:
print("Left is Empty")
parent.left = star
else:
print("Else Left")
self.insert_rec(star)
if parent.right is None:
print("Right is Empty")
parent.right = star
else:
print("Else Right")
self.insert_rec(star)
def main():
# Instantiate Binary Tree to hold the stars
star_tree = Tree("Star Catalog")
with open('HabHYG_short.csv', 'r') as csvfile:
lines = csv.reader(csvfile, delimiter=',')
# skip header row
next(csvfile)
# get time in nanoseconds -- maybe OS-specific?
# See https://docs.python.org/3/library/time.html
t0 = time.perf_counter_ns()
obs_processed = 0
for row in lines:
# hvg_db, name, mag, spectral, habit, dist)
this_star = Star(row[0], row[3], row[16], row[11], row[2], row[12])
star_tree.insert_rec(this_star)
A nice way to handle recursive operations in an object-oriented tree structure is to implement them in the nodes themselves. Create an insert method of TreeNode that recursively inserts a new node somewhere underneath that node. This only requires two decisions:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(self, node):
if node.key < self.key:
# Insert in left subtree, or create it.
if self.left:
self.left.insert(node)
else:
self.left = node
else:
# Insert in right subtree, or create it.
if self.right:
self.right.insert(node)
else:
self.right = node
Then you can build a tree by doing something like:
root = TreeNode(5)
root.insert(TreeNode(3))
root.insert(TreeNode(8))
root.insert(TreeNode(1))
root.insert(TreeNode(4))
root.insert(TreeNode(6))
root.insert(TreeNode(9))
which builds a tree like:
5
/ \
3 8
/ \ / \
1 4 6 9
Writing a function that'll print out a nice tree representation like that is left as an exercise to the reader, but it's easy to mess around with it in the REPL:
>>> from test import *
>>> root.left.left.key
1
>>> root.key
5
>>> root.right.key
8
>>> root.right.right.key
9
The idea of recursion is that you don't need to write a loop that traverses the tree; all you need to do is figure out whether you (the self that insert was called on) know exactly where the new node needs to go, or if you need to hand it off to another node (one of your subtrees) to figure out.
The iteration happens implicitly as each node calls the next one in the chain. Each recursive call just needs to move the execution flow one step closer to where it needs to get.