by A tree is an abstract data type which stores data hierarchically. The top element is known as “Root”. Each node in a tree has a parent node and zero or more children nodes except that Root node which has only children nodes but no parent node.
For eg: a tree can be shown as follows:
Tree Definition:
Formally a tree can be defined as a collection of nodes which follows below properties:
Each node in a tree other than Root node has a unique parent node and every such node is called as child node.
As shown in above diagram “Microsoft” is the Root node which has three children “Office”, “mobile” and “Visual Studio”, which in turn have their own child.
A Generic Tree node can be defined as follows:
// Struct definition for Generic Tree
struct GenericTree
{
int data;
GenericTree* firstChild;
GenericTree* nextSibling;
};
Traversing a Tree:
Accessing or visiting each and every node of a tree is known as traversal of a tree.
Basically there are two kind of traversal mechanism:
1) Preorder traversal:
In this kind of traversal root/parent node is traversed first and then its childrens. So for above shown picture preorder traversal would be as follows:
Microsoft, Office, Excel, Outlook, Word, Powerpoint, Mobile, Lumia, Visual Studio, C++, C#, Dotnet
2) Postorder traversal:
In this kind of traversal root/parent node is traversed after all its children are traversed. So for above shown picture postorder traversal would be as follows:
Excel, Outlook, Word, Powerpoint, Office, Lumia, Mobile, C++, C#, Dotnet, Visual Studio, Microsoft.
Now that we understood basic concept of Tree let’s have a look on below tree structure as shown in below image.
Now lets have a look at the basic code to create above shown tree.
// Create generic tree and returns root node
GenericTree* createRandomGenericTree()
{
GenericTree* root = new GenericTree;
root->data = 10;
root->nextSibling = NULL;
// Adding 4 nodes(2,4,6,8) as child of root
GenericTree* dummy;
GenericTree* temp = new GenericTree();
temp->data = 4;
temp->firstChild = NULL;
temp->nextSibling = NULL;
root->firstChild = temp;
dummy = temp; // This will be used to set next sibling pointer
//Create next node (2)
temp = new GenericTree();
temp->data = 2;
temp->firstChild = NULL;
temp->nextSibling = NULL;
dummy->nextSibling = temp;
dummy = temp;
//Create next node (6)
temp = new GenericTree();
temp->data = 6;
temp->firstChild = NULL;
temp->nextSibling = NULL;
dummy->nextSibling = temp;
dummy = temp;
// Create next node (8)
temp = new GenericTree();
temp->data = 8;
temp->firstChild = NULL;
temp->nextSibling = NULL;
dummy->nextSibling = temp;
//Create next node 11 as child of node 6
temp = new GenericTree();
temp->data = 11;
temp->firstChild = NULL;
temp->nextSibling = NULL;
dummy->firstChild = temp;
// Create next node 13 as child of node 6
temp->nextSibling = new GenericTree();
temp = temp->nextSibling;
temp->data = 13;
temp->firstChild = NULL;
temp->nextSibling = NULL;
return root;
}
Preorder traversal of above shown tree would be as follows:
10, 4, 2, 6, 11, 13, 8
Now let’s have a look at the code for preorder traversal of a tree.
// Function to preorder traversal of a tree. Root node MUST be passed to this function.
void preOrderGenericTree(GenericTree* node)
{
cout << "Preorder Node Data is : " << node->data << endl;
if (node->firstChild)
{
preOrderGenericTree(node->firstChild);
}
if (node->nextSibling)
{
preOrderGenericTree(node->nextSibling);
}
}
Postorder traversal of above shown tree would be as follows:
4, 2, 11, 13, 6, 8, 10
Now let’s have a look at the code for postoder traversal of a tree.
// Function to postorder traversal of a tree. Root node MUST be passed to this function.
void postOrderGenericTree(GenericTree* node)
{
if (node->firstChild)
{
postOrderGenericTree(node->firstChild);
}
cout << "Postorder Node Data is : " << node->data << endl;
if (node->nextSibling)
{
postOrderGenericTree(node->nextSibling);
}
}
For deleting this entire tree, we can write some function which uses any of the above mentioned traversal technique as shown below:
// Function to delete entire tree. Root node MUST be passed to this function.
void deleteGenericTree(GenericTree* node)
{
if (node->firstChild)
{
deleteGenericTree(node->firstChild);
}
if (node->nextSibling)
{
deleteGenericTree(node->nextSibling);
}
cout << "Deleting Node Data is : " << node->data << endl;
delete node;
}
Now, let’s have a look at the sample main function which uses all the above functions:
int main()
{
GenericTree* root;
root = createRandomGenericTree();
preOrderGenericTree(root);
postOrderGenericTree(root);
deleteGenericTree(root);
cout << "All Node data printed" << endl;
}
Output of above program is as follows:
Preorder Node Data is : 10 Preorder Node Data is : 4 Preorder Node Data is : 2 Preorder Node Data is : 6 Preorder Node Data is : 11 Preorder Node Data is : 13 Preorder Node Data is : 8 Postorder Node Data is : 4 Postorder Node Data is : 2 Postorder Node Data is : 11 Postorder Node Data is : 13 Postorder Node Data is : 6 Postorder Node Data is : 8 Postorder Node Data is : 10 Deleting Node Data is : 13 Deleting Node Data is : 11 Deleting Node Data is : 8 Deleting Node Data is : 6 Deleting Node Data is : 2 Deleting Node Data is : 4 Deleting Node Data is : 10 All Node data printed
