Difference between revisions of "Tree (data structure)"
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) (→See also) |
||
| (One intermediate revision by the same user not shown) | |||
| 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 28: | ||
* [[Generative grammar]] | * [[Generative grammar]] | ||
* [[Hierarchy (mathematics)]] | * [[Hierarchy (mathematics)]] | ||
| + | * [[Leaf node]] | ||
* [[Single inheritance]] | * [[Single inheritance]] | ||
* [[Tree (graph theory)]] | * [[Tree (graph theory)]] | ||
Latest revision as of 16:06, 9 May 2016
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).
Not to be confused with
Not to be confused with:
See also
- Abstract data type
- Branching factor
- Computer science
- Computing
- Data structure
- Dialog tree
- Game tree
- Generative grammar
- Hierarchy (mathematics)
- Leaf node
- Single inheritance
- Tree (graph theory)
- Tree (set theory)
- Tree structure
Other trees
External links
- Tree (data structure) @ Wikipedia
