Tree

 Tree

• Definition of Tree: Tree is finite set of nodes with one specially designated node called the root  and the remaining nodes are partitioned into n>=0 disjoint sets T1 & Tn which are called the sub-root trees of the root.

Types of Trees:

• Binary Tree:- 

1. It's finite set of nodes, with one special node called root and the other nodes are partitioned into two disjoints sets, which are binary tree called its left and right subtree.
2.  It is a tree where every nodes can have atmost two branches.

• Stritly  Binary Tree:- 

1. Strictly binary tree is a where all no-leaf nodes have two branches.
2. A Strictly binary tree may not be full.
3. All leaf nodes may not be the same levels.

• Complete Binary Tree(Full Binary Tree):- 

1. Full binary tree of depth d has 2d-1 nodes, In a full binary tree, all the levels are full and all leaf nodes are the same level.
2. Full binary tree is a strictly binary tree.
3. All leaf nodes are the same level

• Al-Most Complete Binary Tree:

1. Binary tree with  d levels is almost complete if level 1 to d-1 are full & last level i.e. level d is partially filled from left to right.
2. Nodes in al-most tree correspond to the nodes which are numbred 1 to n in the full binary tree of depth d.

• Skewed Binary Tree:

1. Left Skwed Binary Tree:- which is having the nodes only in left subtrees. All the right subtrees remains as NULL.

        2.Right Skwed Binary Tree:- which is having the nodes only in right subtrees. All the left                          subtrees remains as NULL.

• Binary Search Tree

1. Binary tree in which nodes are arranged according to their values.
2. The left node a has value < its parent  node and the right node has a value >=  its parent node.

• Expression Tree

1. Expression tree represents an expression operanads and binary operators.
2. The tree strictly binary tree.
3. The operators are in the leaf nodes while the operators are in the parent nodes.

• Heap

1. Heap is complete binary tree in the parent key is  >=  the child key. It's called Max Heap.
2. Heaps where the parent key is <= the child key are called Min-Heap.
3. Heaps are used to repersent priority queues.

        * Definitions:

• Null Tree:- A tree with no nodes is Null Tree. It's also called an empty tree.

• Node:- A node of tree is an item of information along with the branches to other nodes. Example: Tree T has 3 nodes.

• Parent Node:- Parent node is node having other nodes connected to it. These node called are Childern Node. 

• Root:-Root is the parent of all parent nodes.

• Leaf Node:- It is the treminal node of tree. It does not have any child i.e no nodes connected to it. All other nodes are called non-leaf nodes. or internal nodes.

• Siblings:- Childern of the same parent are called siblings.

• Degree of Node:- The number of subtree of nodes is called its degree. The degree of leaf node is '0'(zero).  Example: 'A' having degree 3 then  it's have 3 subtree.

• Degree of Tree:- The degree of a tree is the maximum degree of the nodes in the tree.

• Descendents:- The desendents of the node are all those nodes which are reachable from that node.

• Ancestors:- Which are all the nodes along the path from the root to that node.

• Level of Node:- This indicates the position of a  node in the hierachy. The level of any node = level of its parent +1. The root considered to be at level '0'(zero).

• Height or Depth of Tree:- The  total number of levels in the tree is the height or depth of the tree. The length of longest path from root to any leaf. Maximum height = n. Minimum height = log2n+1. 

• Forest:- It is set of n >= 0 disjoint trees i.e. if we remove the root, we get a forest of trees.

                                                                                                    //ThE ProFessoR