In this article we are going to show you a very simple way to create a graph or a tree structure in C++ and do some operation with them.

Implementation

The idea is real simple, we have to create a struct that contains an object and a pointer or a set of pointers (for example an array) to the memory address of another object.

Binary tree

For example, I want to create a binary tree of int as shown in pic here below.

image

To do that in our struct we need two pointer and an int


#include 
using namespace std;

struct Binary_tree{
    
int data;
Binary_tree* left;
Binary_tree* right;

};

int main()
{
    //Create elements
    Binary_tree* root = new Binary_tree;
    Binary_tree* five = new Binary_tree;
    Binary_tree* eight = new Binary_tree;
    
    //Set data
    
    root->data = 3;
    five->data = 5;
    eight->data = 8;
    
    
    //Set pointers
    
    root->left = eight;
    root->right = five;
    
    five->left = NULL;
    five->right = NULL;
    
    //From c ++ 11 onwards we can use nullptr
    
    eight->left = nullptr;
    eight->right = nullptr;
}


Array Pointer

We can also use an array as a pointer, for example we want to implement the structure below

image

As we can see there are six different pointers. We can use an array of a fixed size to implement this struct.


#include 

using namespace std;

const int size = 6;

struct tree{
    
int data;
tree* ptr[size];

};

int main()
{
    //Create elements
    tree* root = new tree;
    //Set data
    root->data = 5;
    //Set pointers
    
    root->ptr[0] = nullptr;
    root->ptr[1] = nullptr;
    root->ptr[2] = nullptr;
    root->ptr[3] = nullptr;
    root->ptr[4] = nullptr;
    root->ptr[5] = nullptr;
    
}

Data type and list

We can also change the type of data or just implement a struct of pointer without objects. A tree with only one pointer is called list. For example we can develop a tree of string in this way.

image
#include 
#include 
using namespace std;

struct tree{
    
string word;
tree* next;

};

int main()
{
    //Create elements
    tree* root = new tree;
    tree* by = new tree;
    tree* cmp = new tree;
    //Set data
    root->word = "hello";
    by->word = "by";
    cmp->word = "cmp";
    
    //Set pointers
    root->next = by;
    by->next = cmp;
    cmp->next = nullptr;
    
    
}

Count the number of nodes

We can write a function that return the number of the nodes in a tree. We are going to do it in a recursive way. We are using the last tree that we have implemented.


int countNodes(tree* current){
    if(current==NULL)
    return 0;
    return countNodes(current->next)+1;
}

Search element in a tree

In a similar way we can check if an element is in a tree or not

List

tree* findNode(tree* currentNode, string element) {
if (currentNode == NULL || currentNode->word == element)
return currentNode; 
else {
return findNode(currentNode->next, element);
}
}
Binary tree

Binary_tree* findNode(Binary_tree*  currentNode, int element) {
if (currentNode == NULL || currentNode->data == element)
return currentNode; 
else {
Binary_tree*  leftSearchResult = findNode(currentNode->left, element);
Binary_tree*  rightSearchResult = findNode(currentNode->right, element);
if (leftSearchResult == NULL) 
return rightSearchResult;
else
return leftSearchResult;   
 }
 }

That's all!


NEWSLETTER

Do not lose our new articles! Sign up to our newsletter to receive one and only one email every time a new article is online. You will be able to unsubscribe to the service later if you want. What are you waiting for?

Andrea Cappelletti
Programmer / Developer

I really like Linux and its philosophy. I use Arch Linux as OS but at the same time I am very open to all the other OS, indeed I also have installed windows and I have got a MacBook Pro. I fully support Open Source, I usually public software by following this philosophy.