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

Concrete

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.

Array Tree

An array tree numbers the items in a tree numerically, according to potential positions in a hypothetically full tree. This makes for inefficient use of space in storing partial trees, at the benefit of uniform memory access and storage.

To number the tree, construct a breadth-first traversal of each potential node in a hypothetically full tree.

Breadth-first traversal - use queue. Pseudocode:

q = new queue()
p = root()
for c in children(p):
    q.add(c);
while(!q.empty()):
    p = q.pop()
    process(p)
    for c in children(p):
        q.add(c);