Tree

Programming basics

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.

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.

Image of a tree

Access methods of a tree

• enqueue
• dequeue
• isEmpty
• peek

Practical applications of a tree

• Printer queues
• Computer modelling of physical queues (like in a supermarket)

Tree - video example

This video provides a basic introduction to trees. It also summarizes, very nicely, other data structures. Please keep in mind the example is not binary tree, which is different.

Standards

• Describe how trees operate logically (both binary and non-binary).
• Define the terms: parent, left-child, right-child, subtree, root and leaf.
• State the result of inorder, postorder and preorder tree traversal.
• Sketch binary trees.

See Also

• Abstract data structures

Give a sequence of brief answers with no explanation.

Give a detailed account or picture of a situation, event, pattern or process.

Give the precise meaning of a word, phrase, concept or physical quantity.

Give a specific name, value or other brief answer without explanation or calculation.

Give a specific name, value or other brief answer without explanation or calculation.

Represent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.