Home | | Object Oriented Programming and Data Structures | Tree - abstract data type (ADT)

# Tree - abstract data type (ADT)

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, represented as a set of linked nodes.

TREE

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, 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. 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). A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent.

Definition

A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy. A tree can be empty with no nodes called the null or empty tree or a tree is a structure consisting of one node called the root and one or more subtrees.

Terminologies used in Trees

Root - the top most node in a tree.

Parent - the converse notion of child.

Siblings - nodes with the same parent.

Descendant - a node reachable by repeated proceeding from parent to child.

Leaf - a node with no children.

Internal node - a node with at least one child.

Degree - number of sub trees of a node.

Edge - connection between one node to another.

Path - a sequence of nodes and edges connecting a node with a descendant.

Level - The level of a node is defined by 1 + the number of connections between the node and the root.

Height - The height of a node is the length of the longest downward path between the

node and a leaf.

•  Forest - A forest is a set of n ≥ 0 disjoint trees.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Object Oriented Programming and Data Structure : Non-Linear Data Structures : Tree - abstract data type (ADT) |