Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from bt import BTNode
- def count(t):
- ''' (BTNode) -> int
- Return the number of nodes in BTNode t.
- >>> tree = BTNode(5)
- >>> count(tree)
- 1
- >>> b = BTNode(8)
- >>> b = insert(b, 4)
- >>> b = insert(b, 2)
- >>> b = insert(b, 6)
- >>> b = insert(b, 12)
- >>> b = insert(b, 14)
- >>> b = insert(b, 10)
- >>> count(b)
- 7
- '''
- if not t:
- return 0
- elif not t.left and not t.right:
- return 1
- else:
- return count(t.left) + count(t.right) + 1
- def height(t):
- ''' (BTNode) -> int
- Return the number of nodes in longest path in BTNode t.
- >>> tree = BTNode(23)
- >>> height(tree)
- 1
- >>> b = BTNode(8)
- >>> b = insert(b, 4)
- >>> b = insert(b, 2)
- >>> b = insert(b, 6)
- >>> b = insert(b, 12)
- >>> b = insert(b, 14)
- >>> b = insert(b, 10)
- >>> height(b)
- 3
- '''
- if not t:
- return 0
- elif not (t.left or t.right):
- return 1
- else:
- left_node = height(t.left) + 1
- right_node = height(t.right) + 1
- return max([left_node, right_node])
- def leaf_count(t: BTNode) -> int:
- ''' (BTNode) -> int
- Return number of leaf nodes in BTNode t.
- >>> tree = BTNode(17)
- >>> leaf_count(tree)
- 1
- >>> b = BTNode(8)
- >>> b = insert(b, 4)
- >>> b = insert(b, 2)
- >>> b = insert(b, 6)
- >>> b = insert(b, 12)
- >>> b = insert(b, 14)
- >>> b = insert(b, 10)
- >>> leaf_count(b)
- 4
- '''
- if not t:
- return 0
- elif not (t.left or t.right):
- return 1
- else:
- return leaf_count(t.left) + leaf_count(t.right)
- def insert(node, data):
- ''' (BTNode, object) -> BTNode
- Insert data in BST rooted at node if necessary, and return new root.
- >>> b = BTNode(5)
- >>> b1 = insert(b, 3)
- >>> print(b1)
- 5
- 3
- <BLANKLINE>
- '''
- return_node = node
- if not node:
- return_node = BTNode(data)
- elif data < node.data:
- node.left = insert(node.left, data)
- elif data > node.data:
- node.right = insert(node.right, data)
- else: # nothing to do
- pass
- return return_node
- if __name__ == '__main__':
- import doctest
- doctest.testmod()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement