Trees/ADT: Difference between revisions
From charlesreid1
(Created page with "The tree abstract data type can be implelented using object oriented principles. By creating requirements for the methods that a class must implement, we provide assurances th...") |
No edit summary |
||
| Line 26: | Line 26: | ||
* is empty checks if length 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 | 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. | ||
{{TreesFlag}} | |||
[[Category:Trees]] | |||
Revision as of 19:56, 10 June 2017
The tree 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.
Tree abstract data type should implement the following methods:
- size
- iterable
- deplth
- height
- isleaf
- isroot
- getroot
- parent
- children
- 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.
 |
Trees Part of Computer Science Notes
Series on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree · Trees/ArrayTree · SimpleTree
Tree Traversal 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 OOP Principles for Traversal: Tree Traversal/OOP · Tree Traversal/Traversal Method Template Tree operations: Trees/Operations Performance · Trees/Removal
Tree Applications Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree · Binary Trees/ArrayBinTree Binary Trees/Cheat Sheet · Binary Trees/OOP · Binary Trees/Implementation Notes
|