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

Tree abstract data type should implement the following methods:

• size
• iterable
• deplth
• height

• is internal
• is external
• isleaf
• isroot
• root

• parent
• children
• number of children

• all positions

• iterator

Already trees can provide concrete implementations:

• is root just gets root and compares two pointers
• is leaf just checks if num children is 0
• is empty checks if length is 0

At this point you can start designing your concrete implementation, like the Trees/LinkedTree or Trees/ArrayTree implementation, or you can implement a Binary Trees interface and impose further requirements on the class interface and tree structure.