Btree Implementation

#include<iostream>
using namespace std;
template<class T,int m>
class bnode
{
   public:
          int no;                       //total no of keys
          T key[m-1];    
          bnode<T,m> *ptr[m];
          bool leaf;                  //whether its a leaf node or not
       bnode()
        {
           for(int j=0;j<m;j++)
             key[j]=-1;
             leaf=1;
             no=0;
        }
    ~bnode()
     {
         //delete the node
        }
 };
 template<class T,int m>
 class btree
 {
    public:
           bnode<T,m> *root;
         btree()
          {
             bnode<T,m> *root=new bnode<T,m>;
          }
     ~btree()
          { //delete the tree}
       void create();
       void insert(T k);
       void split_child(bnode<T,m> *par,int i,bnode<T,m> *child);
       void insert_nonfull(bnode<T,m> *par,T k);
 };
 template<class T,int m>
 void btree<T,m> ::create()
 {
    bnode<T,m> *z=new bnode<T,m>;
    z->leaf=1;
    z->no=0;
    root=z;
 }
 template<class T,int m>
void btree<T,m>:: insert(T k)
{
  bnode<T,m> *s,*r;
  r=root;
  if(r->no==m-1)
   {
      s=new bnode<T,m>;
      s->leaf=0;
      s->no=0;
      s->ptr[0]=r;
      split_child(s,0,r);
      insert_nonfull(s,k);
   }
  else
    insert_nonfull(s,k);
 }
 template<class T,int m>
 void btree<T,m>::split_child(bnode<T,m> *par,int i,bnode<T,m> *child) 
 {
    int j;
    bnode<T,m> *z=new bnode<T,m>;
    z->leaf=child->leaf;
    z->no=(m/2);
    for(j=0;j<(m/2);j++)
       z->key[j]=child->key[j+(m/2)];
    if(!(child->leaf))
    {
       for(j=0;j<(m/2);j++)
         z->ptr[j]=child->ptr[j+(m/2)+1];
    }
    child->no=(m/2);
    for(j=par->no;j>=i;j--)
      par->ptr[j+1]=par->ptr[j];
    par->ptr[i+1]=z;
    for(j=par->no;j>i;j--)
      par->key[j+1]=par->key[j];
     par->key[i]=child->key[m/2];
     par->no+=1;
  }
  template<class T,int m>
  void btree<T,m>::insert_nonfull(bnode<T,m> *x,T k)
  {
    int i=x->no;
    if(x->leaf)
    {
       while(i>=0&&k<x->key[i])
            x->key[i+1]=x->key[i];
         i-=1;
         x->key[i+1]=k;
         x->no+=1;
     }
     else
     {
       while(i>=0&&k<x->key[i])
          i-=1;
          i+=1;
          if(x->ptr[i]->no==m-1)
             split_child(x,i,x->ptr[i]);
          if(k>x->key[i])
            i=i+1;
          insert_nonfull(x->ptr[i],k);
     }
  }
  int main()
  {
   int x,j;
    btree<int,5> bt;
   cin>>x;
    for(int i=0;i<x;i++)
    {   
        cin>>j;
         bt.insert(j);
   }
    return 0;
  }
   
           
         
  
      
      
            

Huffman tree using C++

#include <iostream>
using namespace std;
#include<string.h>
#include<stdlib.h>


class node
{
 public:
            float freq;                      //number of using character
            char ch[10];                   
            node * right;
            node * left;
   node(float x, node *l=NULL, node *r=NULL)
   {
         freq=x;
         right=r;
         left =l;
   }
};
class tree{
      public:
             node *root;
              
      tree()
      {
            root=NULL;
      }
void sort(node *[], float);
node* create(char[], float);
void right(node *[], int);
void assign_code(node*, int [], int);
void del_tree(node *);
};
node* tree::create(char a[], float x)

{
            node* ptr;
            ptr = new node(x);               //allocate a huffmann node
            ptr->freq = x;              
            strcpy( ptr->ch , a);           //save the character inserted to keep a track 
            ptr->right = NULL;
            ptr->left = NULL;
            return(ptr);                   //return the new huffman node 

}
void tree:: sort(node* a[], float n)

{
    int i, j;
    node* temp;
    for (i = 0; i < n - 1; i++)
       for (j = i; j < n; j++)
          if (a[i]->freq > a[j]->freq)           //sort the huffmann nodes according to increasing frequencies
             {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
          }
}
void tree::right(node* a[], int n)
{
     int i;
      for (i = 1; i < n - 1; i++)
         a[i] = a[i + 1];                          //shift the array to the right by 1
}
void tree:: assign_code(node* tree1, int c[], int n)
{
       int i;
     if ((tree1->left == NULL) && (tree1->right == NULL))
            {
                  cout<<tree1->ch;                       //output the character
              for (i = 0; i < n; i++)
                      cout<< c[i];                    //output the codes
                   cout<<"\n";
            }
     else
        {
                       
            c[n] = 1;                           //assign 1 to the  left node
            n++;
            assign_code(tree1->left, c, n);
            c[n - 1] = 0;                        //assign o to the right node
            assign_code(tree1->right, c, n);
        }
}
void tree::del_tree(node * root)
{
 if(root!=NULL)                              //delete tree
   {
       del_tree(root->left);
       del_tree(root->right);
            delete root;
  }
}
int main()

{
    tree t;
    node* ptr, * head;
              node* a[12];                 //storing the  created  huffmann nodes
           int i, n, total = 0, u, c[15];   //c[15] to store the code 
            char str[10];             
            float f;
          cout<<"HUFFMANN TREE\n";
          cout<<"\nEnter the no. of letter to be coded:";
          cin>>n;
           for (i = 0; i < n; i++)
             {
                  cout<<"Enter the letter & frequency:";
                    cin>>str>>f;
                    cout<<str<<f;
                  a[i] =t.create(str, f);                 //store the created node to the array
                }

            while (n > 1)
             {
                    t.sort(a, n);
                    u = a[0]->freq + a[1]->freq;                //add 1st two lowest frequencies 
                        strcpy(str,a[0]->ch);
                        strcat(str,a[1]->ch);
                        ptr = t.create(str, u);           //create a huffmann node with this addup freq
                        ptr->right = a[1];             //assign the prev nodes to the right of newly created node
                        ptr->left = a[0];              //assign the prev node to the left of newly created node
                        a[0] = ptr;                   //store in the array at 1st index
                        t.right(a, n);               //shift all other nodes to the right
                        n--;
            }

            t.assign_code(a[0], c, 0);
            t.del_tree(a[0]);
            return 0;

}

MULTICASTING IN DELAY TOLERANT NETWORK

Delay Tolerant Network(DTN)s are basically the networks which suffer frequent and long duration partitions.Due to intermittent connectivity in the existing networks,Multicasting in DTN is very challenging.Multicasting means distribution of data to a group of users,which are needed for many potential DTN applications ie.Crisis environments,Deep space communications,Battle Fields,Remote areas etc.It is a new concept brought into picture especially for the hazardous ,unfavourable environments where our infrastructured networks ,Wifi etc fail as they are supposed 2 have end to end connection.DTN doesnt require end to end connection,rather bring forth the stored and forward paradigm.In present scenario,we do hav DAKNET available which are quite similar to DTN,still alot of features absent.Talking about multicasting over DTN....

Multicast supports the distribution of data to a group of users, a service needed for many potential DTN applications. While multicasting in the Internet and mobile ad hoc networks has been studied extensively, due to the unique characteristic of frequent partitioning in DTNs, multicasting in DTNs is a considerably different and challenging problem. It not only requires new definitions of multicast routing algorithms but also brings new issues to the design of routing protocols.

  

 Many potential DTN applications operate in a group-based manner and require efficient network support for group communication. For example, in a disaster recovery scene, it is vital to disseminate information about victims and potential hazards among rescue workers. In a battlefield, soldiers in a squad need to inform each other about their surrounding environment. Although group communication can be implemented by sending a separate unicast packet to each user, this approach suffers from poor performance. The situation is especially acute in DTNs where resources such as connectivity among nodes, available bandwidth and storage are generally severely limited. Thus efficient multicast services are necessary for supporting these applications.

Due to large transfer delays in DTNs, group membership may change during a message transfer, introducing ambiguity in multicast semantics. Under these situations, it is necessary to make a distinction between group members and the intended receivers of a message, i.e., endpoints to which the message should be delivered. Group members may change with time as endpoints join and leave the group. The intended receivers, on the other hand, should be fixed for a message, even though they are defined based on group membership.