Trees/ADT - Revision history

Admin: /* Linked Tree */

2017-06-10T22:11:53Z

Linked Tree

← Older revision		Revision as of 22:11, 10 June 2017
Line 43:		Line 43:

	===Linked Tree===		===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===		===Array Tree===

Admin: /* Array Tree */

2017-06-10T22:09:55Z

Array Tree

← Older revision		Revision as of 22:09, 10 June 2017
Line 50:		Line 50:
	To number the tree, construct a breadth-first traversal of each potential node in a hypothetically full tree.		To number the tree, construct a breadth-first traversal of each potential node in a hypothetically full tree.

	Breadth-first traversal - use queue. Pseudocode:		Breadth-first traversal - use a queue.

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

			Pseudocode:

	<pre>		<pre>

Admin: /* Tree ADT */

2017-06-10T22:09:11Z

Tree ADT

@@ Line 16: / Line 16: @@
 * is internal
 * is external
 * isleaf
@@ Line 32: / Line 32: @@
 * iterator
 Already trees can provide concrete implementations:
@@ Line 39: / Line 41: @@
 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.
 =Flags=

Admin: /* Tree ADT */

2017-06-10T20:26:44Z

Tree ADT

← Older revision		Revision as of 20:26, 10 June 2017
Line 16:		Line 16:


			* is internal
			* is external
	* isleaf		* isleaf
	* isroot		* isroot
	* ~~getroot~~		* root


Line 27:		Line 29:

	* all positions		* all positions

			* iterator

Admin at 20:00, 10 June 2017

2017-06-10T20:00:02Z

← Older revision		Revision as of 20:00, 10 June 2017
Line 1:		Line 1:
	~~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.		==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:		Tree abstract data type should implement the following methods:
Line 27:		Line 35:

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

			=Flags=


	~~{{TreesFlag}}~~
	[[Category:Trees]]		[[Category:Trees]]
			[[Category:ADT]]
	[[Category:Java]]		[[Category:Java]]

			{{TreesFlag}}

Admin at 19:56, 10 June 2017

2017-06-10T19:56:58Z

← Older revision		Revision as of 19:56, 10 June 2017
Line 31:		Line 31:
	{{TreesFlag}}		{{TreesFlag}}
	[[Category:Trees]]		[[Category:Trees]]
			[[Category:Java]]

Admin at 19:56, 10 June 2017

2017-06-10T19:56:42Z

← Older revision		Revision as of 19:56, 10 June 2017
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 ~~Tree~~]] interface and impose further requirements on the class interface and tree structure.		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]]

Admin: 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..."

2017-06-10T19:56:15Z

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..."

New page

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 Tree]] interface and impose further requirements on the class interface and tree structure.