Tree (data structure) - Revision history

Karl Jones: /* See also */

2016-05-09T23:06:21Z

‎See also

Karl Jones: /* See also */

2016-05-09T23:05:17Z

‎See also

Karl Jones: /* See also */

2016-05-09T23:04:40Z

‎See also

Karl Jones: /* See also */

2016-04-26T00:16:23Z

‎See also

Karl Jones: /* See also */

2016-04-26T00:16:13Z

‎See also

Karl Jones: /* See also */

2016-04-26T00:08:31Z

‎See also

Karl Jones: Created page with "In computer science, a '''tree''' is a widely used abstract data type (ADT) — or data structure implementing this ADT — that simulates a hierarchical tree stru..."

2016-04-25T20:42:04Z

Created page with "In computer science, a '''tree''' is a widely used abstract data type (ADT) — or data structure implementing this ADT — that simulates a hierarchical tree stru..."

New page

In [[computer science]], a '''tree''' is a widely used [[abstract data type]] (ADT) — or [[data structure]] implementing this ADT — that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

== Description ==

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node.

Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a list of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance).

For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).

== See also ==

* [[Abstract data type]]
* [[Branching factor]]
* [[Computer science]]
* [[Computing]]
* [[Data structure]]

== External links ==

* [https://en.wikipedia.org/wiki/Tree_(data_structure) Tree (data structure)] @ Wikipedia

[[Category:Computer science]]
[[Category:Data structures]]

← Older revision		Revision as of 23:06, 9 May 2016
Line 10:		Line 10:

	For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).		For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).
		+
		+	== Not to be confused with ==
		+
		+	Not to be confused with:
		+
		+	* [[Tree (set theory)]]

	== See also ==		== See also ==

@@ Line 22: / Line 22: @@
 * [[Generative grammar]]
 * [[Hierarchy (mathematics)]]
 * [[Single inheritance]]
 * [[Tree (graph theory)]]

@@ Line 19: / Line 19: @@
 * [[Data structure]]
 * [[Dialog tree]]
 * [[Generative grammar]]
 * [[Hierarchy (mathematics)]]

@@ Line 23: / Line 23: @@
 * [[Single inheritance]]
 * [[Tree (graph theory)]]
-* [[Tree (set theory)
+* [[Tree (set theory)]]
 * [[Tree structure]]

@@ Line 18: / Line 18: @@
 * [[Computing]]
 * [[Data structure]]
 == External links ==