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) |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.