Binary Trees/ADT

What is an ADT

An abstract data type is a way of providing a consistent interface across multiple data types, so that the underlying implementation of the data structure can be modified without the high level interface or code changing. This is a way of creating more algorithm-independent, abstract code. (To a point.)

An abstract data type can be implelented using object oriented principles. By creating requirements for the methods that a class must implement, we provide assurances that a class provides a specific interface - hopefully without the additional complications of inheritance and full-on class inheritance diagrams.

This page covers the Tree abstract data type. Other types are covered here: Abstract Data Types

Tree ADT

The Trees/ADT provides a set of accessor methods for all trees.

The Binary Trees ADT provides a set of additional accessor methods for abstract binary trees. There is still no useful functionality implemented for creating, modifying, or deleting parts of tree...

Binary Tree ADT

Provides the following additional methods:

• left(p)
• right(p)
• sibling(p)

Can implement children()

• return left and right

Should support iteration

• positions() - get all positions in the tree
• iter() - iterate through all positions in the tree

Concrete Binary Tree

Once you have your concrete binary tree implemented, you will want to have the following methods to modify your tree:

• add root
• add left
• add right
• replace
• delete
• attach