I'm having a bit of difficulty grasping the differences in the methods and implementation of a simple tree, a binary tree, and a binary search tree. It seems that I keep getting confused between the three. I know how to implement a BST. But, I am not too sure about simple trees and a Binary tree. Could somebody show me a simple implementation/code of a tree, and BT. P.S this is not homework, its for me to understand these ADT's
Here is the code for the BST, I have.
"""binary search tree ADT"""
class BST:
def __init__(self: 'BST', root: BTNode=None) -> None:
"""Create BST with BTNode root."""
self._root = root
def __repr__(self: 'BST') -> str:
"""Represent this binary search tree."""
return 'BST(' + repr(self._root) + ')'
def find(self: 'BST', data: object) -> BTNode:
"""Return node containing data, otherwise return None."""
return _find(self._root, data)
def insert(self: 'BST', data: object) -> None:
"""Insert data, if necessary, into this tree.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)), BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
"""
self._root = _insert(self._root, data)
def height(self: 'BST') -> int:
"""Return height of this tree."""
return _height(self._root)
def _insert(node: BTNode, data: object) -> BTNode:
"""Insert data in BST rooted at node, if necessary, and return root."""
if not node:
return 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 node
def _find(node: BTNode, data: object):
"""Return the node containing data, or else None."""
if not node or node.data == data:
return node
else:
if data < node.data:
return _find(node.left, data)
else:
return _find(node.right, data)
def _height(node):
"""Return height of tree rooted at node."""
if not node or node.is_leaf():
return 0
left_h = 0
right_h = 0
if node.left:
left_h = _height(node.left)
if node.right:
right_h = _height(node.right)
return max(left_h, right_h) + 1
class BTNode:
"""Binary Tree node."""
def __init__(self: 'BTNode', data: object,
left: 'BTNode'=None, right: 'BTNode'=None) -> None:
"""Create BT node with data and children left and right."""
self.data, self.left, self.right = data, left, right
def __repr__(self: 'BTNode') -> str:
"""Represent this node as a string."""
return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
', ' + repr(self.right) + ')')
def is_leaf(self: 'BTNode') -> bool:
"""Return True iff BTNode is a leaf"""
return not self.left and not self.right
