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.

Linked Tree

Linked tree data type links the data in the data structure together in memory using links.

Data is contained by wrapper classes (nodes) containing data, which live at particular positions in the tree (represented by another wrapper class).

Much of the behavior comes down to the concrete implementation of linked versus array-based notation.

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 a queue.

Classic fencepost algorithm - loop and a half. Could probably call an "enqueue children" or etc.

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);