Study Guides (238,268)
CSCA48H3 (3)

# week12a48.pdf

5 Pages
278 Views

School
University of Toronto Scarborough
Department
Computer Science
Course
CSCA48H3
Professor
Brian Harrington
Semester
Winter

Description
#================ DATA STRUCTURES ==================# class DLL(object):     def __init__(self, d, prev=None, n=None):         self.data = d         self.prev = prev         self.next = n     def __str__(self):         res = ''         current = self         while current:             res += str(current.data) + ' '             current = current.next         return res class LL(object):     def __init__(self, d, n=None):         self.data = d         self.next = n     def __str__(self):         res = ''         current = self         while current:             res += str(current.data) + ' '             current = current.next         return res class BTNode(object):     def __init__(self, d, l=None, r=None):         self.data = d         self.left = l         self.right = r     def __str__(self):         return str(self.data) class Stack(object):     def __init__(self):         self.stk = []     def pop(self):         return self.stk.pop()     def push(self, k):         self.stk.append(k)     def is_empty(self):         return len(self.stk) == 0     def __str__(self):         return str(self.stk) #=============== EXERCISES IN ORDER ===============# def size(stk):     s = Stack()     c = 0     while not stk.is_empty():         s.push(stk.pop())         c += 1     while not s.is_empty():         stk.push(s.pop())     return c def fib(n):     if n == 1 or n == 2:         return 1     return fib(n­2) + fib(n­1) def make_double_copy(L):     if not L:         return     D = DLL(L.data, None, None)     d_current = D     current = L.next     while current:         d_current.next = DLL(current.data, d_current, None)         d_current = d_current.next         current = current.next     return D def tree_average(root):     (sum, count) = _tree_average(root, 0)     return sum / count def _tree_average(node, count):     '''Return a tuple, (sum, count)'''     if not node:         return (0, 0)     l = _tree_average(node.left, 0)     r = _tree_average(node.right, 0)     return (node.data + l[0] + r[0], 1 + l[1] + r[1]) def leaves_and_internals(node):     '''Return (list of leaves, list of internals).'''
More Less

Related notes for CSCA48H3

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.