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 abstract data type should implement the following methods:
- is internal
- is external
- number of children
- all positions
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 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.
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.
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);
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e