Binary search trees

  • Proposal 1: Write an efficient data structure that can be used for binary trees (containing integer number in nodes)
  • Proposal 2: Design a simple application that can process binary trees.

Propriety

Each node contains an element that is higher than any other element from any node of the left subtree, and smaller or equal than any element from the right subtree (if exists).

Recursively adding a new element in a binary search tree

  • if the tree is NULL, then a new node is created where that element is added;
  • if the tree is not NULL, then:
    • if the root element is > the new element, this is added in the left subtree;
    • if not, it’s added in the right subtree.

Binary trees declaration(search)

typedef int tipDate;
struct nod {
    tipDate info;
    struct nod *st; struct nod *dr;
};
typedef nod * arbore;

Binary search trees – initialisation

int isNullTree(tree a)
{ 
   return (a==NULL); 
}

void initTree(tree& a) 
{ 
   if (!isNullTree(a)) a=NULL; 
}

Adding an element in a binary search tree

bool addToTreeElement(tree& a, tipDate el) {
    if (isNullTree(a)) {
        a=new nod;
        if (!a) return false;
        a->info = el; a->st = NULL; a->dr = NULL;
        return true;
    }
    else if (el < a->info)
        return addToTreeElement(a->st, el);
    else
        return addToTreeElement(a->dr, el);
}

Searching an element in the tree

bool isElementInTree(tree a, tipDate el)
{
    if (!isNullTree(a)) // or if (a)
    {
        if (a->info==el) return true;
        else 
          if (el<a->info) 
             return isElementInTree(a->st, el);
          else 
             return isElementInTree(a->dr, el);
    }
    else
        return false;
}

Crossing binary trees

Preorder:  root, left subtree, right subtree

void preorderCrossing(tree a)
{
    if (!isNullTree(a))
    {
        cout<<a->info<<", ";
        preorderCrossing(a->st);
        preorderCrossing(a->dr);
    }
}

Postorder: left subtree, right subtree, root

void postorderCrossing(arbore a)
{
    if (!isNullTree(a))
    {
        postorderCrossing(a->st);
        postorderCrossing(a->dr);
        cout<<a->info<<", ";
    }
}

Inorder: left subtree, root, right subtree

void inorderCrossing(arbore a)
{
    if (!isNullTree(a))
    {
        inorderCrossing(a->st);
        cout<<a->info<<", ";
        inorderCrossing(a->dr);
    }
}

Demo program

int main() {
    cout << "Binary search trees\n\n";
    tree a; initTree(a);
    unsigned int i; unsigned int n;
    tipDate x;
    cout<<"Number of tree elements: "; cin>>n;
    for (i=1; i<=n; i++) {
        cout<<"Give the "<<i<<"-th element: ";
        cin>>x; addToTreeElement(a,x); 
    }
    cout<<"\nThe elements crossed in inorder are ordered ascending:\n";
    inorderCrossing(a);
    return 0; 
}

Program execution

Graphs

  • Basic notions
  • Representation
  • Prim’s algorithm

Propriety

A graph (undirected or directed) is an ordered pair of sets G=(V,E).
The V set is a non-null set, finite of vertices/nodes of the graph.
The set E is a set of vertices pairs of the graph.
When it comes to undirected graphs, the pairs of vertices of the set E are unordered and they are called edges. The unordered pair formed from the vertices and y is noted as [x,y]; the vertices and y are called the ends of the edge [x,y].
In case of directed graphs, the pairs of vertices from the E set are ordererd and they are called arcs.
If an arc or an edge with ends and y exist, then the vertices and y are adjacent; each end of an edge/arc is considered incident to that respective edge/arc.
We will consider that the ends of an edge, respectively of an arc are distinct (the graph does not have loops).

Visual representation

Adjacency matrix

Let G=(V,E) an undirected graph, with n vertices and m edges. The adjacency matrix associated to G is a square matrix of order n, with elements:

Implementation examples:

int a[100][100];
.................................
cout<<"n="; cin>>n;
//the values of the elements above the main diagonal are read
for (i=1;i<=n-l;i++)
 for (j=i+l; j<=n; j++) { 
   cin>>a[i][j]; 
   //and are transferred below the main diagonal
   a[j][i]=a[i][j];
}
..............................
cin>>n; //node number
cin>>m; //edge number
for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    a[i][j]=0;
for (i=1;i<=m;i++)
{
  cout<<"give the ends of the edge"<<i; 
  cin>>x >>y;
  a[x][y]=1;
  a[y][x]= 1;
}

Adjacency lists

Representation of the graph G by adjacency list is as follows::

  • specyficate the number of vertices, n;
  • for each vertex i, it is specified the list Li of its neighbours, that means the list of nodes adjacent with node i.

Implementation example:

typedef struct nod{
	int inf;
	nod *urm;
}AD;
AD *L[N];  //neighbours' lists
void read()
{
	int i,j,k; 
        AD *x;
	cin>>n; //number of vertices
        cin>>m; //number of edges
        //allocate addresses for neighbours' lists
	for(i=1;i<=n;i++) {
          L[i]=new AD; 
          L[i]->urm=NULL;
	}
	for (k=1;k<=m;k++)
	{	
          cin>>i>>j;
	  //add j in the i's neighbours' list
	  x=new AD; x->inf=j; x->urm=L[i]->urm; L[i]->urm=x;  
	  //add i in the j's neighbours' list
	  x=new AD; x->inf=i; x->urm=L[j]->urm; L[j]->urm=x;  	
	}
}