Forum Comments

Senior2019-Set 4 - Recursive Functions and CNS 4
In ACSL Contest Prep
chris13888
Nov 17, 2019
a = input() class Node():    def __init__(self, value, depth=0):        self.value = value        self.left = self.right = None        self.depth = depth    def insert(self, value):        if value <= self.value:            if self.left == None:                self.left = Node(value, self.depth+1)                # print(f'{value} is the left child of {self.value}')            else:                self.left.insert(value)        if value > self.value:            if self.right == None:                self.right = Node(value, self.depth+1)                # print(f'{value} is the right child of {self.value}')            else:                self.right.insert(value)    def children(self):        children = 0        if self.left != None: children += 1        if self.right != None: children += 1        return children    def match(self, other):        if self.left == None and self.right == None:            return True        if other.left == None and self.left != None:            return False        if other.right == None and self.right != None:            return False        if self.left == None:            return self.right.match(other.right)        if self.right == None:            return self.left.match(other.left)        return self.left.match(other.left) and self.right.match(other.right)    def traverse(self):        # print(self.value, self.left, self.right)        yield self        if self.left != None:            yield from self.left.traverse()        if self.right != None:            yield from self.right.traverse() A = Node(a[0]) for c in a[1:]:    A.insert(c) leaf = external = external_path = internal_path = depth = 0 for node in A.traverse():    if node.children() == 0:        leaf += 1        external += 2        external_path += 2*(node.depth+1)    if node.children() == 1:        external += 1        external_path += node.depth+1    internal_path += node.depth    depth = max(node.depth, depth) print(depth, leaf, external, internal_path, external_path)
0
0
c
chris13888
More actions