Trees In C++: Basic Terminology, Traversal Techniques & C++ Tree Types

This In-depth Tutorial On C++ Trees Explains Tree Types, Tree Traversal Techniques and Basic Terminology With Pictures And Example Programs:

In this C++  Series, so far we have seen the linear data structure of both static and dynamic nature. Now we will proceed with the non-linear data structure. The first data structure in this category is “Trees”.

Trees are non-linear hierarchical data structures. A tree is a collection of nodes connected to each other by means of “edges” which are either directed or undirected. One of the nodes is designated as “Root node” and the remaining nodes are called child nodes or the leaf nodes of the root node.

In general, each node can have as many children but only one parent node.

=> Check Out The Entire C++ Training Series

Nodes of a tree are either at the same level called sister nodes or they can have a parent-child relationship. Nodes with the same parent are sibling nodes.

Trees In C++

Given below is an Example tree with its various parts.

Let us go through the definitions of some basic terms that we use for trees.

• Root node: This is the topmost node in the tree hierarchy. In the above diagram, Node A is the root node. Note that the root node doesn’t have any parent.
• Leaf node: It is the Bottom node in a tree hierarchy. Leaf nodes are the nodes that do not have any child nodes. They are also known as external nodes. Nodes E, F, G, H, and C in the above tree are all leaf nodes.
• Subtree: Subtree represents various descendants of a node when the root is not null. A tree usually consists of a root node and one or more subtrees. In the above diagram, (B-E, B-F) and (D-G, D-H) are subtrees.
• Parent node: Any node except the root node that has a child node and an edge upward towards the parent.
• Ancestor Node: It is any predecessor node on a path from the root to that node. Note that the root does not have any ancestors. In the above diagram, A and B are the ancestors of E.
• Key: It represents the value of a node.
• Level: Represents the generation of a node. A root node is always at level 1. Child nodes of the root are at level 2, grandchildren of the root are at level 3, and so on. In general, each node is at a level higher than its parent.
• Path: The path is a sequence of consecutive edges. In the above diagram, the path to E is A=>B->E.
• Degree: The degree of a node indicates the number of children that a node has. In the above diagram, the degree of B and D is 2 each whereas the degree of C is 0.

Types Of C++ Trees

The tree data structure can be classified into the following subtypes as shown in the below diagram.

#1) General Tree

The general tree is the basic representation of a tree. It has a node and one or more child nodes. The top-level node i.e. the root node is present at level 1 and all the other nodes may be present at various levels.

A General Tree is shown in the below figure.

As shown in the above figure, a general tree may contain any number of subtrees. The nodes B, C, and D are present at level 2 and are sibling nodes. Similarly, nodes E, F, G, and H are also sibling nodes.

The nodes present at different levels may exhibit a parent-child relationship. In the above figure, nodes B, C and D are children of A. Nodes E and F are children of B whereas nodes G and H are children of D.

The general tree is demonstrated below using the C++ implementation:

#include <iostream>
using namespace std;

//declaration for new tree node
struct node  { 
int data; 
struct node *left; 
struct node *right; 
}; 
  
//allocates new node 
struct node* newNode(int data) { 
  // declare and allocate new node  
  struct node* node = new struct node(); 
  
  node->data = data;    // Assign data to this node
  
  // Initialize left and right children as NULL 
node->left = NULL; 
node->right = NULL; 
return(node); 
} 
  
int main() { 
  /*create root node*/
struct node *rootNode = newNode(10);  
cout<<"General tree created is as follows:"<<endl;
cout<<"\t\t\t "<<rootNode->data<<endl;
cout<<"\t\t\t "<<"/ "<<"\\"<<endl; rootNode->left        = newNode(20); 
rootNode->right       = newNode(30); 
cout<<"\t\t\t"<<rootNode->left->data<<"  "<<rootNode->right->data;
cout<<endl; rootNode->left->left  = newNode(40); 
cout<<"\t\t\t"<<"/"<<endl;
cout<<"\t\t      "<<rootNode->left->left->data;
   
return 0; 
}

Output:

General tree created is as follows:

10

/ \

20  30

/

40

#2) Forests

Whenever we delete the root node from the tree and the edges join the next level elements and the root, we obtain disjoint sets of trees as shown below.

In the above figure, we obtained two forests by deleting the root node A and the three edges that were connecting the root node to nodes B, C, and D.

#3) Binary Tree

A tree data structure in which each node has at most two child nodes is called a binary tree. A binary tree is the most popular tree data structure and is used in a range of applications like expression evaluation, databases, etc.

The following figure shows a binary tree.

In the above figure, we see that nodes A, B, and D have two children each. A binary tree in which each node has exactly zero or two children is called a full binary tree. In this tree, there are no nodes that have one child.

A complete binary tree has a binary tree that is completely filled with the exception of the lowest level that is filled from left to right. The binary tree shown above is a full binary tree.

Following is a simple program to demonstrate a binary tree. Note that the output of the tree is the in-order traversal sequence of the input tree.

#include<iostream>
using namespace std;

struct bintree_node{
	bintree_node *left;
	bintree_node *right;
	int data;
} ;
class bst{
	bintree_node *root;
	public:
	bst(){
		root=NULL;
	}
	int isempty() {
		return(root==NULL);
	}
	void insert(int item);
	void displayBinTree();
	void printBinTree(bintree_node *);
	
};
void bst::insert(int item){
	bintree_node *p=new bintree_node;
	bintree_node *parent;
	p->data=item;
	p->left=NULL;
	p->right=NULL;
	parent=NULL;
	if(isempty())
		root=p;
	else{
		bintree_node *ptr;
		ptr=root;
		while(ptr!=NULL){
			parent=ptr;
			if(item>ptr->data)		
				ptr=ptr->right;
			else
				ptr=ptr->left;
		}	
		if(item<parent->data)
			parent->left=p;
		else
			parent->right=p;
	}
}
void bst::displayBinTree(){
	printBinTree(root);
}
void bst::printBinTree(bintree_node *ptr){
	if(ptr!=NULL){
		printBinTree(ptr->left);
		cout<<"  "<<ptr->data<<" "; 
                printBinTree(ptr->right);
	}
}
int main(){
	bst b;
	b.insert(20);
	b.insert(10);
	b.insert(5);
	b.insert(15);
	b.insert(40);
	b.insert(45);
	b.insert(30); 
	
	cout<<"Binary tree created: "<<endl;
	b.displayBinTree();	
}

Output:

Binary tree created:

5       10       15       20       30       40       45

#4) Binary Search Tree

The binary tree that is ordered is called the binary search tree. In a binary search tree, the nodes to the left are less than the root node while the nodes to the right are greater than or equal to the root node.

An example of a binary search tree is shown below.

In the above figure, we can see that the left nodes are all less than 20 which is the root element. The right nodes, on the other hand, are greater than the root node. The binary search tree is used in searching and sorting techniques.

#5) Expression Tree

A binary tree that is used to evaluate simple arithmetic expressions is called an expression tree.

A simple expression tree is shown below.

In the above sample expression tree, we represent the expression (a+b) / (a-b). As shown in the above figure, the non-leaf nodes of the tree represent the operators of the expression while the leaf nodes represent the operands.

Expression trees are mainly used to solve algebraic expressions.

Tree Traversal Techniques

We have seen linear data structures like arrays, linked lists, stacks, queues, etc. All these data structures have a common traversing technique that traverses the structure only in one way i.e. linearly.

But in the case of trees, we have different traversal techniques as listed below:

#1) In order: In this traversal technique, we traverse the left subtree first till there are no more nodes in the left subtree. After this, we visit the root node and then proceed to traverse the right subtree until there are no more nodes to traverse in the right subtree. Thus the order of inOrder traversal is left->root->right.

#2) Pre-order: For the preorder traversal technique, we process the root node first, then we traverse the entire left subtree, and finally, we traverse the right subtree. Hence the order of preorder traversal is root->left->right.

#3) Post-order: In the post-order traversal technique, we traverse the left subtree, then the right subtree, and finally the root node. The order of traversal for the postorder technique is left->right->root.

If n is the root node and ‘l’ and ’r’ are left and right nodes of the tree respectively, then the tree traversal algorithms are as follows:

In order (lnr) algorithm:

1. Traverse left subtree using inOrder(left- Subtree).
2. Visit the root node(n).
3. Traverse right subtree using inOrder(right- subtree).

Preorder (nlr) algorithm:

1. Visit the root node(n).
2. Traverse left subtree using preorder(left-subtree).
3. Traverse the right subtree using preorder(right-subtree).

Postorder (lrn) algorithm:

1. Traverse left subtree using postOrder(left-subtree).
2. Traverse the right subtree using postOrder(right-subtree).
3. Visit the root node(n).

From the above algorithms of traversal techniques, we see that the techniques can be applied to a given tree in a recursive fashion to get the desired result.

Consider the following tree.

Using the above traversal techniques, the traversal sequence for the above tree is given below:

1. InOrder traversal : 2 3 5 6 10
2. PreOrder traversal : 6 3 2 5 10
3. PostOrder traversal: 2 5 3 10 6

Conclusion

Trees are a non-linear hierarchical data structure that is used in many applications in the software field.

Unlike linear data structures that have only one way to traverse the list, we can traverse trees in a variety of ways. We had a detailed study of traversal techniques and the various types of trees in this tutorial.

=> Take A Look At The C++ Beginners Guide Here