document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. from bt import BTNode
  2.  
  3. def count(t):
  4. ''' (BTNode) -> int
  5.  
  6. Return the number of nodes in BTNode t.
  7.  
  8. >>> tree = BTNode(5)
  9. >>> count(tree)
  10. 1
  11. >>> b = BTNode(8)
  12. >>> b = insert(b, 4)
  13. >>> b = insert(b, 2)
  14. >>> b = insert(b, 6)
  15. >>> b = insert(b, 12)
  16. >>> b = insert(b, 14)
  17. >>> b = insert(b, 10)
  18. >>> count(b)
  19. 7
  20. '''
  21. if not t:
  22. return 0
  23. elif not t.left and not t.right:
  24. return 1
  25. else:
  26. return count(t.left) + count(t.right) + 1
  27.  
  28. def height(t):
  29. ''' (BTNode) -> int
  30.  
  31. Return the number of nodes in longest path in BTNode t.
  32.  
  33. >>> tree = BTNode(23)
  34. >>> height(tree)
  35. 1
  36. >>> b = BTNode(8)
  37. >>> b = insert(b, 4)
  38. >>> b = insert(b, 2)
  39. >>> b = insert(b, 6)
  40. >>> b = insert(b, 12)
  41. >>> b = insert(b, 14)
  42. >>> b = insert(b, 10)
  43. >>> height(b)
  44. 3
  45. '''
  46.  
  47. if not t:
  48. return 0
  49. elif not (t.left or t.right):
  50. return 1
  51. else:
  52. left_node = height(t.left) + 1
  53. right_node = height(t.right) + 1
  54. return max([left_node, right_node])
  55.  
  56.  
  57. def leaf_count(t: BTNode) -> int:
  58. ''' (BTNode) -> int
  59.  
  60. Return number of leaf nodes in BTNode t.
  61.  
  62. >>> tree = BTNode(17)
  63. >>> leaf_count(tree)
  64. 1
  65. >>> b = BTNode(8)
  66. >>> b = insert(b, 4)
  67. >>> b = insert(b, 2)
  68. >>> b = insert(b, 6)
  69. >>> b = insert(b, 12)
  70. >>> b = insert(b, 14)
  71. >>> b = insert(b, 10)
  72. >>> leaf_count(b)
  73. 4
  74. '''
  75.  
  76. if not t:
  77. return 0
  78. elif not (t.left or t.right):
  79. return 1
  80. else:
  81. return leaf_count(t.left) + leaf_count(t.right)
  82.  
  83.  
  84. def insert(node, data):
  85. ''' (BTNode, object) -> BTNode
  86.  
  87. Insert data in BST rooted at node if necessary, and return new root.
  88.  
  89. >>> b = BTNode(5)
  90. >>> b1 = insert(b, 3)
  91. >>> print(b1)
  92. 5
  93. 3
  94. <BLANKLINE>
  95. '''
  96. return_node = node
  97. if not node:
  98. return_node = BTNode(data)
  99. elif data < node.data:
  100. node.left = insert(node.left, data)
  101. elif data > node.data:
  102. node.right = insert(node.right, data)
  103. else: # nothing to do
  104. pass
  105. return return_node
  106. if __name__ == '__main__':
  107. import doctest
  108. doctest.testmod()
');