Free text books

Tree in Data structure

TREE : A tree is a non linear data structure . Each object of a tree starts with a trunk or root and extends into several branches . Each branch may extend into other branches until finally terminated by a leaf .

Examples of Tree :

  • Tree can be viewed as lineage of a person that is referred to as the family tree .
  • Organizational chart of a company .

In computer applications , a tree is an hierarchical collection of finite elements . Each element is called a node .

Terms related to tree structure

  • Root Node : The unique node in the tree that has no parent node is called the root node or root of the tree . It represents the beginning of the tree .
  • Parent Node : The node, which generates links for other nodes , is known as the parent node . The parent node is always above its child nodes .
  • Child Node : The node that is directly connected to a parent node is called the child node .
  • Subtree : The child node of the root node that has its own child nodes is called the subtree .
  • Terminal Nodes : The node having no successor or cjild is called the terminal node .
  • Siblings: The nodes having a common parent are called siblings . These are children of the same parent node .
  • Depth of Node: Each node has a unique path connecting it to the root . The depth of a node is the total number of nodes between the node and the root , including the root itself . The depth of root node is 0 .
  • Hieght of tree : The maximum depth among all of the nodes of a tree is called the height of tree .
  • Empty Tree : A tree that has no node is called empty Tree . Its height is -1 .
  • Degree of Node : The number of children of a node is called degree of the node .

Types of Tree :

  • Singleton Tree : The tree whose root us its only node is called the singleton .
  • Full Tree : A tree is called the full tree if all its internal nodes have the same degree and all the leaves are at the same level .
  • Binary Tree : A binary tree is a hierarchical collection of a finite number of nodes in which each node can have a maximum of two children . A binary tree may be empty or non empty but a general tree cannot be empty . One child is on theleft side and other is on the right side of the tree or subtree .
    • Full binary tree : A binary tree is said to be full binary tree when 1. Its all leaves are at same level . 2. Every node has two children I.e left child and right child .
    • Extended Binary Tree (2_Tree) : A binary tree in which each node has either no child or two children is called an extended binary tree .
    • Complete Binary Tree: A binary tree is said to be a complete binary tree of height H if
      • All nodes at level H_2 and above have two children each .
      • A node at level H_1 has one child , it is a left child and all left siblings of the node have two children each .
  • Binary Search Tree : A binary tree in which the left child node of a tree or subtree has lesser value than its root node but right child node has greater (or equal) value than its root node is called binary search tree (BST) .

Leave a Reply

Your email address will not be published. Required fields are marked *