**Tree:** A tree is a data structure similar to a linked list list but instead of each node pointing simply to to the next node in a linear fashion, each node points to a number of nodes.

Tree is a example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.

The graph theoretic definition of tree is " It is a finite set of one or more data items such that

1. There is a special data item called the root of the tree.

2. And its remaining data items are partitioned into number of multiple exclusive subsets, each of which itself a tree and they are called sub trees.

### Tree Terminology

**1. ROOT:-** It is a specially designated item in a tree. It is the first in the hierarchical arrangement of data items. In the above tree, "A" is the root item.

**2. NODE:**- Each data item in a tree is called node. It is the basic structure in a tree. It specifies the data information and links to other data item. There are 10 nodes in the above tree.

**3. LEAF NODE:-** A node with no children is called a leaf node, which is not a leaf is called internal node.

**4. PATH:- **In a tree data structure, the sequence of nodes and edges from one node to another node is called as PATH between that two nodes. Length of a path is total number of nodes in this path.

Example: A-D-G-J

**5.SIBLINGS:-** The children of the same parent are called siblings.

Example: B and E are siblings

**6. ANCESTOR AND DESCENDANT:**- If there is a path between A and B, then A is called an ancestor of B and B is called a descendant of A.

**7. SUB TREE:-** Any node of a tree, with all of its descendants is a sub tree.

**8. LEVEL:-** The level of the node refers to its distance from the root. The root of the tree has level zero. The maximum number of nodes at any level is 2 power n.

**9. HEIGHT:-** The maximum level in a tree determines its height. The height of a node in a tree is the length of a longest path from the node to a leaf. The term depth is also used to denote height of the tree.

**10. DEPTH:-** The depth of a node is the number of nodes is the number of nodes along the path from the root to that node.

## 0 comments:

## Post a Comment

Note: only a member of this blog may post a comment.