Tree Data Structure

Tree Data Structure || Type of Tree Data Structure || Tree in Data Structure || What is Tree ? || Tree Terminology in Data Structure

Here i am discussing the what is Tree Data Structure ?, Tree Data Structure kya Hota Hai ?, bellow the content shown...

A Tree is a collection of elements called nodes each nodes contains some value or elements. We will use term node rather than vertex in a tree.

Note :- Element collector is called node in tree terminology & called vertex in graph terminology.

Node is the main component of any tree structure its store the actual data along with links to the other nodes.

Note :- Link is generally called edges in tree data structure.

A Tree ‘T’ is represented by node & edges which includes :-

i. ‘T’ is empty (called null or empty tree)

ii. ‘T’ has at least one left sub tree or one right sub tree.

Tree Terminology

Types of Tree

Binary Tree :- In a Binary Tree every node except leaf node must contain at most two children

Ternary Tree :- Ina Ternary tree every node except leaf node must contains at most three children.

N-ary Tree :- Ina N Ary tree every node except leaf node must contains at most n children.

Left Skewed Tree :- LSBT is the part of binary tree, in this tree all children present in the tree is left on root node.

Right Skewed Tree :- RSBT is the part of binary tree, in this tree all children present in the tree is right on root node.

Full Binary Tree :- A binary tree is a full binary tree if and only if-

i. Each non-leaf node has exactly two children

ii. All leaf node are at some level.

Complete Binary Tree :- A Binary tree is said to be complete binary tree if –

i. All its levels except possible the last have the maximum no of nodes AND :-

ii. All the node at the last level appears as far as possible. (its means filling nodes form left towards right)

Strict Binary Tree :- When every non leaf node in binary tree is field with left and right sub tree is called strict binary tree.

In other words we can say that every non leaf node has exactly two children.

Binary Tree Representation

Memory Representation

Let ‘T’ be a binary tree these are two ways of representation ‘T’ in memory as follow

i. Link representation of ‘T’ :- Consider a Binary tree ‘T’.

‘T’ will be maintain in memory by means of a linked representation which uses parallel array information left right.

First of all each node ‘N’ of ‘T’ with correspond to location ‘K’ such that

=> Info [K] contain a data part of node

=> Left [K] contain the location of the left child.

=> Right [K] contain the location of the right child.

ii. Sequential representation of Binary tree

Suppose ‘T’ is a binary tree that is complete or nearly complete.

Then there is an efficient way of representing ‘T’ in memory called sequential representation pr Array Representation