document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. from tree import *
  2. from csc148_queue import Queue
  3.  
  4. def arity(t):
  5. ''' (Tree) -> int
  6.  
  7. Return the maximum branching factor of Tree t.
  8.  
  9. >>> tn2 = Tree(2, [Tree(4), Tree(4.5), Tree(5), Tree(5.75)])
  10. >>> tn3 = Tree(3, [Tree(6), Tree(7)])
  11. >>> tn1 = Tree(1, [tn2, tn3])
  12. >>> arity(tn1)
  13. 4
  14. '''
  15. if not t.children:
  16. return 0
  17.  
  18. else:
  19. return_list = [arity(x) for x in t.children]
  20. return_list.append(len(return_list))
  21. return max(return_list)
  22.  
  23. def count(t):
  24. ''' (Tree) -> int
  25.  
  26. Return the number of nodes in Tree t.
  27.  
  28. >>> tree = Tree(5)
  29. >>> count(tree)
  30. 1
  31. >>> tree = descendents_from_list(Tree(7), [2, 3, 4, 5, 6], 3)
  32. >>> count(tree)
  33. 6
  34. '''
  35. if not t.children:
  36. return 1
  37.  
  38. else:
  39. return_list = sum([count(x) for x in t.children]) + 1
  40. return return_list
  41.  
  42. def height(t):
  43. ''' (Tree) -> int
  44.  
  45. Return 1 + the number of nodes in longest path in Tree t.
  46.  
  47. >>> tree = Tree(23)
  48. >>> height(tree)
  49. 1
  50. >>> tree = descendents_from_list(Tree(11), [2, 3, 4, 5, 6], 3)
  51. >>> height(tree)
  52. 3
  53. '''
  54. if not t.children:
  55. return 1
  56. else:
  57. return_value = max([height(x) for x in t.children])
  58. return_value += 1
  59. return return_value
  60.  
  61. def leaf_count(t: Tree) -> int:
  62. ''' (Tree) -> int
  63.  
  64. Return number of leaf nodes in Tree t.
  65.  
  66. >>> tree = Tree(17)
  67. >>> leaf_count(tree)
  68. 1
  69. >>> tree = descendents_from_list(Tree(17), [2, 3, 4, 5, 6, 7, 8, 9], 3)
  70. >>> leaf_count(tree)
  71. 6
  72. '''
  73. if not t.children:
  74. return 1
  75. else:
  76. return_list = sum([leaf_count(x) for x in t.children])
  77. return return_list
  78.  
  79. if __name__ == '__main__':
  80. import doctest
  81. doctest.testmod()
');