Tree

From Computer Science Wiki
Programming basics[1]

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.[2]


Image of a tree[edit]

Binary tree.svg.png

Access methods of a tree[edit]

  • enqueue
  • dequeue
  • isEmpty
  • peek

Practical applications of a tree[edit]

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

Tree - video example[edit]

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. Ignore the discussion about cousins and uncles. It's ridiculous. But the rest of the video is good.

Standards[edit]

  • 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[edit]

References[edit]