from tree import *
from csc148_queue import Queue
def arity(t):
''' (Tree) -> int
Return the maximum branching factor of Tree t.
>>> tn2 = Tree(2, [Tree(4), Tree(4.5), Tree(5), Tree(5.75)])
>>> tn3 = Tree(3, [Tree(6), Tree(7)])
>>> tn1 = Tree(1, [tn2, tn3])
>>> arity(tn1)
4
'''
if not t.children:
return 0
else:
return_list = [arity(x) for x in t.children]
return_list.append(len(return_list))
return max(return_list)
def count(t):
''' (Tree) -> int
Return the number of nodes in Tree t.
>>> tree = Tree(5)
>>> count(tree)
1
>>> tree = descendents_from_list(Tree(7), [2, 3, 4, 5, 6], 3)
>>> count(tree)
6
'''
if not t.children:
return 1
else:
return_list = sum([count(x) for x in t.children]) + 1
return return_list
def height(t):
''' (Tree) -> int
Return 1 + the number of nodes in longest path in Tree t.
>>> tree = Tree(23)
>>> height(tree)
1
>>> tree = descendents_from_list(Tree(11), [2, 3, 4, 5, 6], 3)
>>> height(tree)
3
'''
if not t.children:
return 1
else:
return_value = max([height(x) for x in t.children])
return_value += 1
return return_value
def leaf_count(t: Tree) -> int:
''' (Tree) -> int
Return number of leaf nodes in Tree t.
>>> tree = Tree(17)
>>> leaf_count(tree)
1
>>> tree = descendents_from_list(Tree(17), [2, 3, 4, 5, 6, 7, 8, 9], 3)
>>> leaf_count(tree)
6
'''
if not t.children:
return 1
else:
return_list = sum([leaf_count(x) for x in t.children])
return return_list
if __name__ == '__main__':
import doctest
doctest.testmod()