Tree Data Structures

‘Tree’ is an Abstract Data Type that simulates hierarchical tree like structure. Tree begins with only one node at the highest level called as ‘root’. In tree, one node points to another in hierarchical manner, without pointing in reverse and without duplication.



Constraints for Tree
1. There is only one root to tree data structure.
2. There is no reference to root node.
3. There is only one reference to a node i.e. a node can have only one parent node.

Terminologies used in Trees
• Root – The top node in a tree.
• Parent – The converse notion of a child.
• Siblings – Nodes with the same parent.
• Descendant – A node reachable by repeated proceeding from parent to child.
• Ancestor – A node reachable by repeated proceeding from child to parent.
• Leaf – A node with no children.
• Internal node – A node with at least one child.
• External node – A node with no children.
• Degree – Number of sub trees of a node.
• Edge – Connection between the nodes.
• Path – A sequence of nodes and edges connecting a node with a descendant.
• Level – The level of a node is defined by 1 + (the number of connections between the node and the root).
• Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.
• Height of tree – The height of a tree is the height of its root node.
• Depth – The depth of a node is the number of edges from the node to the tree's root node.
• Forest – A forest is a set of n ≥ 0 disjoint trees.

Types of Trees
Following are various types of trees widely used in DS applications:-
i. Binary Tree
ii. Binary Search Tree
    a. Self-Balancing (Binary Search Tree)
        • AVL tree
        • Red-Black tree
        • AA tree
    b. Splay Trees
    c. Treaps (Tree Heaps)
iii. B trees
      a. A B tree
      b. A B+ tree
iv. Complete tree

Tree traversal
Following are the ways in which a tree can be traversed.
1. Depth First
    a. Pre-order traversal
    b. In-order traversal
    c. Post-order traversal
2. Breadth First
(Binary trees are used to demonstrate traversal)

Application of trees
i. Representing hierarchical data.
ii. Sorting
iii. Routing


Implementation of tree traversal
Binary trees are used to demonstrate traversal. All variants of binary trees can be traversed using these methods.

Code:
 
#include "iostream"
 
using namespace std;
 
class node{
                public:
                                int data;
                                class node *left;
                                class node *right;
               
                public:
                                node(int in_data){
                                                data = in_data;
                                                left = NULL;
                                                right = NULL;
                                }
                               
                                void print(){
                                                cout << data;
                                }
};
 
void InorderTraverse(node *temp){
               
                if(temp == NULL)
                                return;
               
                InorderTraverse(temp->left);
                cout << "  "<<temp->data;
                InorderTraverse(temp->right);
}
 
void PreorderTraverse(node *temp){
               
                if(temp == NULL)
                                return;
               
                cout << "  "<<temp->data;
                PreorderTraverse(temp->left);
                PreorderTraverse(temp->right);
}
 
void PostorderTraverse(node *temp){
               
                if(temp == NULL)
                                return;
               
                PostorderTraverse(temp->left);
                PostorderTraverse(temp->right);
                cout << "  "<<temp->data;
}
 
void PrintLevelOrder(node *root){
                node *queue[100];
                int i = 0;
               
                for(i=0; i<100; i++)
                                queue[i] = NULL;
               
                int first = 0, last = 0;
               
                node *temp = root;
               
                while(temp!=NULL){
                                cout << " " << temp->data;
                               
                                if(temp->left)
                                                queue[last++] = temp->left;
                                if(temp->right)
                                                queue[last++] = temp->right;
                               
                                temp = queue[first++];
                }
}
 
int main(){
               
                node *root;
               
                root = new node(10);
                root->left = new node(20);
                root->right = new node(30);
                root->left->left = new node(40);
                root->left->right = new node(50);
                root->right->left = new node(60);
                root->right->right = new node(70);
                cout << "\nTree used is: ";
                cout << "\n         10";
                cout << "\n        /  \\";
                cout << "\n      20    30";
                cout << "\n     / \\   /  \\";
                cout << "\n    40  50 60  70";
                cout << "\n";
                /*
                                                     10
                                                      /   \
                                                  20     30
                                                 /  \      / \
                                             40 50  60 70
                */
                cout<<"\n\nDepth First Search (DFS):\n";
                cout << "\nInorder Traversal : ";
                InorderTraverse(root);
                cout << "\nPreorder Traversal : ";
                PreorderTraverse(root);
                cout << "\nPostorder Traversal : ";
                PostorderTraverse(root);
                cout<<"\n\nBreadth First Search (BFS):\n";
                cout<<"\nLevel order traversal: ";
                PrintLevelOrder(root);
                               
                return 0;                             
}
 
Output:
 
 
Tree used is:
          10
        /     \
      20      30
     / \        /  \
    40  50 60  70
 
 
Depth First Search (DFS):
 
Inorder Traversal :   40  20  50  10  60  30  70
Preorder Traversal :   10  20  40  50  30  60  70
Postorder Traversal :   40  50  20  60  70  30  10
 
Breadth First Search (BFS):
 
Level order traversal:  10 20 30 40 50 60 70


 

1 comment :