Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement