TREE

TREE

================================================================================

• A Tree is a non-linear data structure and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

• A tree consists of a root, and zero or more subtrees T₁, T₂, … , T_k such that there is an edge from the root of the tree to the root of each subtree.

• Basic Terminologies: 

• Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}.

• Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D, E} are the child nodes of {B}.

• Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.

• Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M, N, O, P} are the leaf nodes of the tree.

• Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are the ancestor nodes of the node {E}

• Descendant: Any successor node on the path from the leaf node to that node. {E,I} are the descendants of the node {B}.

• Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.

• Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.

• Internal node: A node with at least one child is called Internal Node.

• Neighbor of a Node: Parent or child nodes of that node are called neighbors of that node.

• Subtree: Any node of the tree along with its descendant.

• Properties

• Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes then it will have (N-1) edges. There is only one path from each node to any other node of the tree.

• Depth of a node: The depth of a node is defined as the length of the path from the root to that node. Each edge adds 1 unit of length to the path. So, it can also be defined as the number of edges in the path from the root of the tree to the node

• Height of a node: The height of a node can be defined as the length of the longest path from the node to a leaf node of the tree.

• Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a leaf node of the tree.

• Degree of a Node: The total count of subtrees attached to that node is called the degree of the node. The degree of a leaf node must be 0. The degree of a tree is the maximum degree of a node among all the nodes in the tree.

  
  

• Basic Operation:  
• Create – create a tree in data structure.
• Insert − Inserts data in a tree.
• Search − Searches specific data  in a tree to check it is present or not.
  

• Preorder Traversal – Perform Traveling a tree in a pre-order manner in data structure .

• In order Traversal – Perform Traveling a tree in an in-order manner.

• Post order Traversal – Perform Traveling a tree in a post-order manner.

• Types: 
• Binary Tree
• Binary Search Tree
• Complete Binary Tree
• Strictly Binary Tree
• Full Binary Tree
• Almost Complete Binary Tree
• Threaded Binary Tree
• Skewed Binary Tree
• Balanced Binary Tree
• AVL Tree
• B Tree
• B + Tree

• Preorder Traversal:
• NLR ==> Node Left Right
• Algorithm:

• void preorder(node *T)

  {

              if (T != NULL)

              {

                          write(T -> data)

                          preorder(T -> Left)

                          preorder(T -> Right)

  }

  }

  
  

• eg.










• OUTPUT ==> A B D E F C G H

• Inorder Traversal:
• LNR ==> Left Node Right
• Algorithm:

• void inorder(node *T)

  {

              if (T != NULL)

              {

                          inorder(T -> Left)

                          write(T -> data)

                          inorder(T -> Right)

  }

  }

  
  
• eg.

• OUTPUT ==> B E D F A G C H

• Postorder Traversal:
• LRN ==> Left Right Node
• Algorithm:

• void postorder(node *T)

  {

              if (T != NULL)

              {

                         postorder(T -> Left)

  postorder(T -> Right)

                         write(T -> data)

  }

  }

• eg. 

• OUTPUT ==> E F D B G H C A