Search This Blog

Thursday, April 05, 2012

INTODUCTION TO DATA STRUCTURES IN C++

INTODUCTION TO DATA STRUCTURES IN C++

CONTENTS
  • I. ASSUMPTIONS
  • II. INTRODUCTION
  • III. STACKS
  • IV. QUEUES
  • V. LINKED LISTS
  • VI. STACKS USING LINKED LISTS
  • VII. QUEUES USING LINKED LISTS
  • VIII. CIRCULAR QUEUES
  • IX. BINARY SEARCH TREES
  • X. CONTACT ME
I. ASSUMPTIONS

In this Tutorial I assume that all of you have a working knowledge on how to use
Classes in C++ because all of my data structures are going to be based on them.
I realised that there are a lot of Data Structures Tutorials available but it's
rare to find one that uses OOP. So this one will mainly focus on having a data
structure incorporated as a class.
CODE IS COMPILED IN BORLAND C++ UNLESS OTHERWISE MENTIONED.

II. INTRODUCTION


We shall cover the following Basic Data Structures in this Tutorial:

1. STACKS
2. QUEUES
3. LINKED LISTS
4. BINARY TREES

We shall also combine data structures together later in this tutorial such as
combining a Linked List along with a Stack etc. We shall also learn about Doubly
Linked Lists and Circular Linked Lists in this Tutorial.

So let's begin without wasting any time.


III. STACKS

Stacks are commonly used Data Structures while writing code. It's concept is
really simple which makes it even simpler to write it in code. Consider this
situation. There are a pile of 5 Books on a Table. You want to add one book to
the pile. What do you do??? You simply add the book on the TOP of the pile. What
if you want the third book from the new 6 book pile? You then lift each book one
by one from the TOP until the third book reaches the top. Then you take the
third book and replace all the others back into the pile by adding them from the
TOP.
If you've noticed I've mentioned the word TOP in Caps. Yes, TOP is the most
important word as far as stacks are concerned. Data is stored in a Stack where
adding of data is permitted only from the top. Removing/Deleting Data is also
done from the top. As Simple as That. Now you may ask where Stacks are used?
Stacks are infact used on every Processor. Each processor has a stack where data
and addresses are pushed or added to the stack. Again the TOP rule is followed
here. The ESP Register adds as a Stack Pointer that refers to the top of the
stack in the Processor. Anyway, since the explaination of how the Processor
Stack works is beyond the subject of this Tutorial, let's write our Stack Data
Structure. Remember some Stack Terminology before continuing. Adding Data to the
Stack is known as Pushing and deleting data from the stack is known as Popping.


01#include
02 
03using namespace std;
04 
05#define MAX 10        // MAXIMUM STACK CONTENT
06 
07 
08class stack
09{
10 
11  private:
12    int arr[MAX];   // Contains all the Data
13    int top;        //Contains location of Topmost Data pushed onto Stack
14 
15  public:
16     stack()         //Constructor
17     {
18        top=-1;      //Sets the Top Location to -1 indicating an empty stack
19     }
20 
21     void push(int a)  // Push ie. Add Value Function
22     {
23        top++;        // increment to by 1
24        if(top
25         {
26            arr[top]=a;  //If Stack is Vacant store Value in Array
27         }
28         else
29         {
30            cout<<"STACK FULL!!"<<endl;
31            top--;
32         }
33     }
34 
35    int pop()                  // Delete Item. Returns the deleted item
36    {
37        if(top==-1)
38        {
39            cout<<"STACK IS EMPTY!!!"<<endl;
40            return NULL;
41        }
42        else
43        {
44            int data=arr[top];     //Set Topmost Value in data
45            arr[top]=NULL;       //Set Original Location to NULL
46            top--;               // Decrement top by 1
47            return data;         // Return deleted item
48        }
49     }
50};
51 
52 
53int main()
54{
55 stack a;
56 a.push(3);
57 cout<<"3 is Pushed\n";
58 a.push(10);
59 cout<<"10 is Pushed\n";
60 a.push(1);
61 cout<<"1 is Pushed\n\n";
62 
63 cout<pop()<<" is Popped\n";
64 cout<pop()<<" is Popped\n";
65 cout<pop()<<" is Popped\n";
66 return 0;
67}


OUTPUT:
3 is Pushed
10 is Pushed
1 is Pushed

1 is Popped
10 is Popped
3 is Popped


Clearly we can see that the last data pushed is the first one to be popped out.
That's why a Stack is also known as a LIFO Data Structure which stands for "Last
In,First Out" and I guess you know why.

Let us see how we implemented the stack. We first created a variable called top
that points to the top of the stack. It is initialised to -1 to indicate that
the stack is empty. As Data is entered, the value in top increments itself and
data is stored into an array arr. Now there's one drawback to this Data
Structure. Here we state the Maximum number of elements as 10. What if we need
more than 10 Data Elements? In that case we combine a Stack along with a Linked
List which will be explained later.
Now once you've got this one right, let's proceed to the Queue Data Structure.


IV. QUEUES

There's a huge crowd at your local grocery store. There are too many people
trying to buy their respective items and the Shopkeeper doesnt know from where
to start. Everyone wants their job done quickly and the shopkeeper needs an
efficient method to solve this problem. What does he do? He introduces a Queue
System based on the First Come, First Serve System. The Last Person trying to
buy an item stands behind the last person at the END of the queue. The
Shopkeeper however is present at the FRONT end of the queue. He gives the item
to the person in FRONT of the queue and after the transaction is done, the
person in FRONT of the Queue Leaves. Then the person second in queue becomes the
First person in the Queue.

Do you get the point here? A Queue is similar to a stack except that addition of
data is done in the BACK end and deletion of data is done in the FRONT.
Writing a queue is a lot harder than writing a stack. We maintain 2 Integers in
our Queue Data Structure, one signifying the FRONT end of the Queue and the
other referring to the BACK end of the Queue.

Let us use the same coding style as we used for the Stack. We first initialise
both the ends to -1 to indicate an empty queue. When Data is added to the queue
both ends get respective postive values. When New Data is added, the back End is
incremented and when data is deleted the front end is decremented. This works
fine but it has a major drawback. What if the Maximum capacity of the Queue is 5
Items. Suppose the User has added 4 items, deleted 3 items and adds 2 again. The
Stack wont permit him to add the last half of the data as it will report that
the stack is full. The Reason is that we are blindly incrementing/decrementing
each end depending on addition/deletion not realising that both the ends are
related to each other. I leave this as an excercise for you to answer. Why will
our proposed Stack report the Stack as Full even though it's actually vacant?
So we need another approach.In this method we focus more on the data than on the
addition end and the deletion end.

What we now use is the grocery store example again. Suppose there are 5 items in
a queue and we want to delete them one by one. We first delete the first data
item pointed by the deletion end. Then we shift all data one step ahead so that
the second item becomes the first, third item becomes second and so on...
Another method would be to maintain the difference between the two ends which is
not practical. Hence we stick to our previous method. It might be slow in Big
Queues, but it certainly works great. Here's the code.

001#include
002 
003using namespace std;
004 
005#define MAX 5           // MAXIMUM CONTENTS IN QUEUE
006 
007 
008class queue
009{
010 private:
011    int t[MAX];
012    int al;      // Addition End
013    int dl;      // Deletion End
014 
015 public:
016  queue()
017  {
018    dl=-1;
019    al=-1;
020  }
021 
022  void del()
023  {
024     int tmp;
025     if(dl==-1)
026     {
027        cout<<"Queue is Empty";
028     }
029     else
030     {
031        for(int j=0;j<=al;j++)
032        {
033            if((j+1)<=al)
034            {
035                tmp=t[j+1];
036                t[j]=tmp;
037            }
038            else
039            {
040                al--;
041 
042            if(al==-1)
043                dl=-1;
044            else
045                dl=0;
046            }
047        }
048     }
049  }
050 
051void add(int item)
052{
053    if(dl==-1 && al==-1)
054    {
055        dl++;
056        al++;
057    }
058   else
059   {
060        al++;
061        if(al==MAX)
062    {
063            cout<<"Queue is Full\n";
064            al--;
065            return;
066        }
067    }
068    t[al]=item;
069 
070}
071 
072  void display()
073  {
074    if(dl!=-1)
075   {
076    for(int iter=0 ; iter<=al ; iter++)
077        cout<" ";
078   }
079   else
080    cout<<"EMPTY";
081  }
082 
083};
084 
085int main()
086{
087 queue a;
088 int data[5]={32,23,45,99,24};
089 
090 cout<<"Queue before adding Elements: ";
091 a.display();
092 cout<<endl<<endl;
093 
094 for(int iter = 0 ; iter < 5 ; iter++)
095 {
096   a.add(data[iter]);
097   cout<<"Addition Number : "<<(iter+1)<<" : ";
098   a.display();
099   cout<<endl;
100 }
101 cout<<endl;
102 cout<<"Queue after adding Elements: ";
103 a.display();
104 cout<<endl<<endl;
105 
106 for(iter=0 ; iter < 5 ; iter++)
107 {
108   a.del();
109   cout<<"Deletion Number : "<<(iter+1)<<" : ";
110   a.display();
111   cout<<endl;
112 }
113 return 0;
114}


OUTPUT:
Queue before adding Elements: EMPTY

Addition Number : 1 : 32
Addition Number : 2 : 32 23
Addition Number : 3 : 32 23 45
Addition Number : 4 : 32 23 45 99
Addition Number : 5 : 32 23 45 99 24

Queue after adding Elements: 32 23 45 99 24

Deletion Number : 1 : 23 45 99 24
Deletion Number : 2 : 45 99 24
Deletion Number : 3 : 99 24
Deletion Number : 4 : 24
Deletion Number : 5 : EMPTY



As you can clearly see through the output of this program that addition is
always done at the end of the queue while deletion is done from the front end of
the queue. Once again the Maximum limit of Data will be extended later when we
learn Linked Lists.


V. LINKED LISTS

The Linked List is a more complex data structure than the stack and queue. A
Linked List consists of two parts, one the DATA half and the POINTER half. The
Data half contains the data that we want to store while the pointer half
contains a pointer that points to the next linked list data structure. This way
we have a dynamic data structure as we can add as much data as we want within
memory restrictions. And yes, pointers play a major role in Data Structures...No
Pointers, No Data Structures...So Knowledge of Pointers is a basic must before
continuing.
Look at this diagram that explains the Linked List:

Items Added in Link List : 12 15 29 45
http://www.dreamincode.net/forums/index.php?act=Attach&type=post&id=7757

Here the data stored within the Data Structure is 12,15,29,45.
As you can see, the pointer with 12 points to the next linked list which is 15
which points to 29 and so on.
This is just a conceptual idea. In Reality all this data is stored in random
places in memory. Using Pointers help us to get all the data in order.
While Adding Data to a Linked List we check for previously added Linked Lists.
Then we reach the last node of the List where the pointer value is NULL and
point it to our newly created linked list, else if there is no previously
existing linked list we simply add one and set it's pointer to NULL.
Deletion is more complex. Suppose we want to delete the data 15. Then we first
find 15. Then we point the pointer which is present with 12 to the data in 29.
Then we delete the node which contains 15 as it's data.
Studying the Following Source code will help you understand and Appreciate the
Linked List:

001#include
002using namespace std;
003 
004class linklist
005{
006    private:
007 
008     struct node
009         {
010            int data;
011            node *link;
012         }*p;
013 
014   public:
015 
016         linklist();
017         void append( int num );
018         void add_as_first( int num );
019         void addafter( int c, int num );
020         void del( int num );
021         void display();
022         int count();
023         ~linklist();
024};
025 
026linklist::linklist()
027{
028    p=NULL;
029}
030 
031void linklist::append(int num)
032{
033   node *q,*t;
034 
035   if( p == NULL )
036   {
037      p = new node;
038      p->data = num;
039      p->link = NULL;
040   }
041   else
042   {
043      q = p;
044      while( q->link != NULL )
045        q = q->link;
046 
047      t = new node;
048      t->data = num;
049      t->link = NULL;
050      q->link = t;
051   }
052}
053 
054void linklist::add_as_first(int num)
055{
056   node *q;
057 
058   q = new node;
059   q->data = num;
060   q->link = p;
061   p = q;
062}
063 
064void linklist::addafter( int c, int num)
065{
066   node *q,*t;
067   int i;
068   for(i=0,q=p;i
069   {
070      q = q->link;
071      if( q == NULL )
072      {
073        cout<<"\nThere are less than "<" elements.";
074        return;
075      }
076   }
077 
078   t = new node;
079   t->data = num;
080   t->link = q->link;
081   q->link = t;
082}
083 
084void linklist::del( int num )
085{
086   node *q,*r;
087   q = p;
088   if( q->data == num )
089   {
090      p = q->link;
091      delete q;
092      return;
093   }
094 
095   r = q;
096   while( q!=NULL )
097   {
098      if( q->data == num )
099      {
100         r->link = q->link;
101         delete q;
102         return;
103      }
104 
105      r = q;
106      q = q->link;
107   }
108   cout<<"\nElement "<" not Found.";
109}
110 
111void linklist::display()
112{
113   node *q;
114   cout<<endl;
115 
116   for( q = p ; q != NULL ; q = q->link )
117    cout<<endl<data;
118 
119}
120 
121int linklist::count()
122{
123   node *q;
124   int c=0;
125   for( q=p ; q != NULL ; q = q->link )
126    c++;
127 
128   return c;
129}
130 
131linklist::~linklist()
132{
133   node *q;
134   if( p == NULL )
135    return;
136 
137   while( p != NULL )
138   {
139      q = p->link;
140      delete p;
141      p = q;
142   }
143}
144 
145int main()
146{
147   linklist ll;
148   cout<<"No. of elements = "<
149   ll.append(12);
150   ll.append(13);
151   ll.append(23);
152   ll.append(43);
153   ll.append(44);
154   ll.append(50);
155 
156   ll.add_as_first(2);
157   ll.add_as_first(1);
158 
159   ll.addafter(3,333);
160   ll.addafter(6,666);
161 
162   ll.display();
163   cout<<"\nNo. of elements = "<
164 
165   ll.del(333);
166   ll.del(12);
167   ll.del(98);
168   cout<<"\nNo. of elements = "<
169   return 0;   
170}


OUTPUT:
No. of elements = 0

1
2
12
13
333
23
43
666
44
50
No. of elements = 10
Element 98 not Found.
No. of elements = 8


Here as you see, the class contains a structure node that consists of an integer
type for data and a pointer pointing to another node structure. Here we maintain
a node pointer p that always points to the first item in the list. Here is a
list of the functions that are used in the data structure.
1linklist();                       // CONSTRUCTOR
2void append( int num );           // ADD AT END OF LIST
3void add_as_first( int num );     // ADD TO BEGINNING OF LIST
4void addafter( int c, int num );  // ADD DATA num AFTER POSTION c
5void del( int num );              // DELETE DATA num
6void display();                   // DISPLAY LINKED LIST
7int count();                      // NUMBER OF ITEMS IN LIST
8~linklist();                      // DESTRUCTOR


Many places you will see statements like q=q->link inside a loop. This statement
just shifts the pointer from one node to the other. the Destructor as well as
the del() function use the delete operator to deallocate space that was
previously allocated by the new operator. The Rest should be clear if you have a
basic understanding of pointers.

The advantage of using pointers is that you dont have to worry about wasting
space by allocating a lot of memory beforehand. As the need for data increases,
memory is allocated accordingly. But the flip side is that to access each node
we have to iterate through each node till we reach the desired node. That's why
linked lists have different forms of themselves for easier access. For example
Circular and Doubly Linked Lists. Circular Linked Lists are those in which the
last node always points to the first node in the list. Doubly Linked Lists
contain two pointers, one that points to the next node and the other that points
to the previous node.

I shall only give source code for Circular Linked List, while code for doubly
linked lists is given as an excercise. However, if you cant write it...you are
free to contact me at born2c0de AT dreamincode DOT net

VI. STACKS USING LINKED LISTS

Here, we use the same concept of the stack but eliminate the MAXIMUM data items
constraint. Since we shall be using Linked Lists to store data in the stack,
the Stack can hold as much as data as it wants as long as the data is within
Memory Limits.Here's the code:

01#include
02 
03using namespace std;
04 
05struct node
06{
07   int data;
08   node *link;
09};
10 
11class lstack
12{
13      private:
14              node* top;
15 
16      public:
17             lstack()
18             {
19                top=NULL;
20             }
21              
22             void push(int n)
23             {
24                node *tmp;
25                tmp=new node;
26                if(tmp==NULL)
27                   cout<<"\nSTACK FULL";
28                    
29                tmp->data=n;
30                tmp->link=top;
31                top=tmp;
32             }
33 
34             int pop()
35             {
36                if(top==NULL)
37                {
38                    cout<<"\nSTACK EMPTY";
39                    return NULL;
40                }
41                node *tmp;
42                int n;
43                tmp=top;
44                n=tmp->data;
45                top=top->link;
46                delete tmp;
47                return n;
48             }
49 
50             ~lstack()
51             {
52                if(top==NULL)
53                   return;
54 
55                node *tmp;
56                while(top!=NULL)
57                {
58                   tmp=top;
59                   top=top->link;
60                   delete tmp;
61                }
62             }
63};
64 
65int main()
66{
67    lstack s;
68    s.push(11);
69    s.push(101);
70    s.push(99);
71    s.push(78);
72    cout<<"Item Popped = "<pop()<<endl;
73    cout<<"Item Popped = "<pop()<<endl;
74    cout<<"Item Popped = "<pop()<<endl;
75    return 0;
76}




VII. QUEUES USING LINKED LISTS

Similar to the one above, the queued linked list removes the maximum data limit
as well. Here is the code:

01#include
02 
03using namespace std;
04 
05struct node
06{
07   int data;
08   node *link;
09};
10 
11class lqueue
12{
13 private:
14    node *front,*rear;
15 
16 public:
17    lqueue()
18    {
19        front=NULL;
20        rear=NULL;
21    }
22 
23    void add(int n)
24    {
25        node *tmp;
26        tmp=new node;
27        if(tmp==NULL)
28           cout<<"\nQUEUE FULL";
29 
30        tmp->data=n;
31        tmp->link=NULL;
32        if(front==NULL)
33        {
34            rear=front=tmp;
35            return;
36        }
37            rear->link=tmp;
38            rear=rear->link;
39    }
40 
41    int del()
42    {
43        if(front==NULL)
44        {
45            cout<<"\nQUEUE EMPTY";
46            return NULL;
47        }
48        node *tmp;
49        int n;
50        n=front->data;
51        tmp=front;
52        front=front->link;
53        delete tmp;
54        return n;
55    }
56 
57    ~lqueue()
58    {
59        if(front==NULL)
60           return;
61        node *tmp;
62        while(front!=NULL)
63        {
64            tmp=front;
65            front=front->link;
66            delete tmp;
67        }
68     }
69};
70 
71int main()
72{
73    lqueue q;
74    q.add(11);
75    q.add(22);
76    q.add(33);
77    q.add(44);
78    q.add(55);
79    cout<<"\nItem Deleted = "<
80    cout<<"\nItem Deleted = "<
81    cout<<"\nItem Deleted = "<
82    return 0;
83}



VIII. CIRCULAR QUEUES

Circular Linked Lists are just like normal linked lists except that the pointer
of the last item in the list points to the first item in the list. You must be
wondering...Why would anyone ever want to do such a thing? Well...did you know
that circular linked lists are used almost in every situation, they are infact
used in Electronic Advertisements where each ad is added to the list and is
displayed. After the last ad is displayed the linked list will automatically
display the first ad in the List.

Now let us see how we can implement the Circular Linked List. I've written this
code in much more detail plus I've included a SLIDESHOW Feature that shows the
Data in the List after a time-period is elapsed. It goes on displaying the data
until a key is pressed. Have a look:

*Note*:
If you aren't using Windows, follow these steps:
  • Remove #include
  • Remove #include
  • Remove the slideshow() and wait() function from CL_list class.
  • Remove the slideshow() function call in main().
001#include
002#include
003#include
004 
005using namespace std;
006 
007 
008class CL_list
009{
010   private:
011      struct node
012      {
013        int data;
014        node *link;
015      };
016      struct node *p;
017 
018   public:
019      CL_list();
020      CL_list(CL_list& l);
021      ~CL_list();
022      void add(int);
023      void del();
024      void addatbeg(int);
025      void display();
026      void slideshow(float,int,int);
027      int count();
028      void wait(float);
029      bool operator ==(CL_list);
030      bool operator !=(CL_list);
031      void operator =(CL_list);
032};
033 
034   CL_list::CL_list()
035   {
036      p=NULL;
037   }
038 
039   CL_list::CL_list(CL_list& l)
040   {
041      node *x;
042      p=NULL;
043      x=l.p;
044      if(x==NULL)
045        return;
046      for(int i=1;i<=l.count();i++)
047      {
048        add(x->data);
049         x=x->link;
050      }
051   }
052 
053   CL_list::~CL_list()
054   {
055    node *q,*t;
056      q=p;
057      t=p;
058      if(p==NULL)
059        return;
060      while(q->link!=t)
061      {
062        p=q;
063         q=q->link;
064         delete p;
065      }
066      p=q;
067      delete p;
068   }
069 
070   void CL_list::add(int n)
071   {
072      if(p==NULL)
073      {
074         node *q;
075         q=new node;
076         q->data=n;
077         q->link=q;
078         p=q;
079         return;
080      }
081      node *q;
082      q=p;
083      while(q->link != p)
084        q=q->link;
085 
086      node *t;
087      t=new node;
088      t->data=n;
089      t->link=p;
090      q->link=t;
091   }
092 
093   void CL_list::display()
094   {
095      if(p==NULL)
096      {
097        cout<<"EMPTY LIST\n";
098         return;
099      }
100      node *q;
101      q=p;
102      for(int i=1;i<=this->count();i++)
103      {
104         cout<data<<endl;
105         q=q->link;
106      }
107   }
108 
109   int CL_list::count()
110   {
111      node *q;
112      q=p;
113      int c=0;
114      if(p==NULL)
115        return 0;
116      else
117        c++;
118      while(q->link != p)
119      {
120         c++;
121         q=q->link;
122      }
123      return c;
124   }
125 
126   void CL_list::del()
127   {
128      if(p==NULL)
129        return;
130      if(p->link==p)
131      {
132        p=NULL;
133      }
134      else
135      {
136      node *q;
137      q=p;
138      while(q->link != p )
139        q=q->link;
140 
141      q->link=p->link;
142      q=p;
143      p=(q->link == NULL ? NULL : p->link);
144      delete q;
145      }
146 
147   }
148 
149   void CL_list::addatbeg(int n)
150   {
151      node *q,*t;
152      q=p;
153      while(q->link!=p)
154        q=q->link;
155 
156      t=new node;
157      t->data=n;
158      t->link=p;
159      q->link=t;
160      p=t;
161   }
162 
163   void CL_list::slideshow(float dlay,int x,int y)
164   {
165    /*  if(p==NULL)
166      {
167         gotoxy(x,y);
168        cout<<"EMPTY LIST\n";
169         return;
170      }
171      node *q;
172      q=p;
173      while(!kbhit())
174      {
175         gotoxy(x,y);
176         cout<<"               ";
177         gotoxy(x,y);
178         cout<data;
179         wait(dlay);
180         q=q->link;
181      }*/
182   }
183 
184   void CL_list::wait(float t)
185   {
186      long time=GetTickCount()+(t*1000L);
187      while(GetTickCount()<=time)
188      {
189      /*        WAIT !!! */
190      }
191   }
192 
193   bool CL_list::operator ==(CL_list t)
194   {
195      if(t.p==NULL && p==NULL)
196        return 1;
197 
198      if(this->count() != t.count())
199        return 0;
200      node *q;
201      q=p;
202      bool flag;
203      flag=1;
204      node *a;
205      a=t.p;
206      for(int i=1;i<=count();i++)
207      {
208        if(a->data!=q->data)
209           flag=0;
210         a=a->link;
211         q=q->link;
212      }
213      if(a->data!=q->data)
214        flag=0;
215      return flag;
216   }
217 
218   bool CL_list::operator !=(CL_list t)
219   {
220    return !(this->operator==(t));
221   }
222 
223 
224   int main()
225   {
226 
227      CL_list a;
228      a.add(1);
229      a.add(2);
230      a.add(3);
231      a.add(4);
232      a.addatbeg(128);
233      a.del(); // 128 is deleted
234      cout<<"\nLIST DATA:\n";
235      a.display();
236 
237      CL_list b=a;
238      if(b!=a)
239        cout<<endl<<"NOT EQUAL"<<endl;
240      else
241        cout<<endl<<"EQUAL"<<endl;
242      a.slideshow(1,13,13);
243 
244      return 0;
245}


Here once again we have made sure that the last node always points to the first
node. Everything else seems fine. Comments should be enough to explain the code.
The interesting part of this code is the slideshow() function. It plainly
displays the list in an infinite loop which can be terminated by pressing a key.
The wait() function allows the delay while the kbhit() function checks for a
keypress.
Now comes the test. Write a similar linked list only with the following changes:
1) Structure node should be like this:
1struct node
2       {
3         int data;
4         node *next;  // Pointer to Next Node
5         node *prev;  // Pointer to Previous Node
6       };


2) Remember that while adding and deleting the next and previous pointers have
to be set up accordingly.

3) Include a display function with a parameter like this:
01void linklist::display(int type)
02      {
03           if(type==1)
04           {
05            // Code for output from First Node to Last node
06           }
07           else
08           {
09            // Code for output from Last Node to First
10           }
11      }

This function is really easy to write if you understand how to use both the next
and previous pointers.

If you still cant write the code mail me with your difficulties at my email add:
born2c0de AT dreamincode DOT net

IX. BINARY SEARCH TREES

Uptil now all data structures that we have covered (Stack,Queue,Linked List) are
linear in nature ie. they have a definate order of placement. Now we shall study
Binary Trees which requires a different thought process as it is a non linear
data structure.

A Binary Tree consists of a main node known as the Root. The Root then has two
sub-sections, ie. the left and the right half. The data subsequently stored
after the root is created depends on it's value compared to the root.
Suppose the root value is 10 and the Value to be added is 15, then the data is
added to the right section of the root.
The Basic idea is that every node can be thought of a binary tree itself. Each
node has two pointers, one to the left and the other to the right. Depending on
the value to be stored, it is placed after a node's right pointer if the value
of the node is lesser than the one to be added or the node's left pointer if
viceversa.

Let's take an Example. To add the Following List of Numbers, we end up with a
Binary Tree like this:

32 16 34 1 87 13 7 18 14 19 23 24 41 5 53

http://www.dreamincode.net/forums/index.php?act=Attach&type=post&id=7756

Here's How:
**: KEEP ADDING DATA IN THE TREE ON PAPER AFTER EACH STEP BELOW TO UNDERSTAND
HOW THE TREE IS FORMED.
  • Since 32 is the First Number to be added, 32 becomes the root of the tree.
  • Next Number is 16 which is lesser than 32 Hence 16 becomes left node of 32.
  • 34. Since 34 > 32 , 34 becomes the right node of the ROOT.
  • 1. Since 1 < 32 we jump to the left node of the ROOT. But since the left node
    has already been taken we test 1 once again. Since 1 < 16, 1 becomes the left
    node of 16.
  • 87. Since 87 > 32 we jump to the right node of the root. Once again this
    space is occupied by 34. Now since 87 > 34, 87 becomes the right node of 34.
  • 13. Since 13 < 32 we jump to left node of the root. There, 13 < 16 so we
    continue towards the left node of 16. There 13 > 1, so 13 becomes the right
    node of 1.
  • Similarly work out addition till the end ie. before Number 53.
  • 53. Since 53 > 32 we jump to the right node of the root. There 53 > 34 so we
    continue to the right node of 34. There 53 < 87 so we continue towards the
    left node of 87. There 53 > 41 so we jump to the right node of 41. Since the
    Right node of 41 is empty 53 becomes the right node of 41.
This should give you an idea of how a Binary Tree works. You must know that:
  • The linking of nodes to nodes in a Binary Tree is one to one in nature
    ie. a node cannot be pointed by more than 1 node.
  • A Node can point to two different sub-nodes at the most.
Here in the binary tree above there are a few nodes whose left and right
pointers are empty ie. they have no sub-node attached to them. So Nodes 5,14,18,
19,23,24,41 have their left nodes empty.

There are three popular ways to display a Binary Tree. Displaying the trees
contents is known as transversal. There are three ways of transversing a tree iw.
in inorder,preorder and postorder transversal methods. Description of each is
shown below:

PREORDER:
  • Visit the root.
  • Transverse the left leaf in preorder.
  • Transverse the right leaf in preorder.
INORDER:
  • Transverse the left leaf in inorder.
  • Visit the root.
  • Transverse the right leaf in inorder.
POSTORDER:
  • Transverse the left leaf in postorder.
  • Transverse the right leaf in postorder.
  • Visit the root.
Writing code for these three methods are simple if we understand the recursive
nature of a binary tree. Binary tree is recursive, as in each node can be
thought of a binary tree itself. It's just the order of displaying data that
makes a difference for transversal.

Deletion from a Binary Tree is a bit more difficult to understand. For now just
remember that for deleting a node, it is replaced with it's next inorder
successor. I'll explain everything after the Binary Tree code.
Now that you've got all your Binary Tree Fundas clear, let's move on with the
Source code.

001#include
002 
003using namespace std;
004 
005#define YES 1
006#define NO 0
007 
008class tree
009{
010    private:
011        struct leaf
012        {
013            int data;
014            leaf *l;
015            leaf *r;
016        };
017        struct leaf *p;
018 
019    public:
020        tree();
021        ~tree();
022        void destruct(leaf *q);
023        tree(tree& a);
024        void findparent(int n,int &found,leaf* &parent);
025        void findfordel(int n,int &found,leaf *&parent,leaf* &x);
026        void add(int n);
027        void transverse();
028        void in(leaf *q);
029        void pre(leaf *q);
030        void post(leaf *q);
031        void del(int n);
032};
033         
034tree::tree()
035{
036    p=NULL;
037}
038 
039tree::~tree()
040{
041    destruct(p);
042}
043 
044void tree::destruct(leaf *q)
045{
046    if(q!=NULL)
047    {
048        destruct(q->l);
049        del(q->data);
050        destruct(q->r);
051    }
052}
053void tree::findparent(int n,int &found,leaf *&parent)
054{
055    leaf *q;
056    found=NO;
057    parent=NULL;
058 
059    if(p==NULL)
060        return;
061 
062    q=p;
063    while(q!=NULL)
064    {
065        if(q->data==n)
066        {
067            found=YES;
068            return;
069        }
070        if(q->data>n)
071        {
072            parent=q;
073            q=q->l;
074        }
075        else
076        {
077            parent=q;
078            q=q->r;
079        }
080    }
081}
082 
083void tree::add(int n)
084{
085    int found;
086    leaf *t,*parent;
087    findparent(n,found,parent);
088    if(found==YES)
089        cout<<"\nSuch a Node Exists";
090    else
091    {
092        t=new leaf;
093        t->data=n;
094        t->l=NULL;
095        t->r=NULL;
096 
097        if(parent==NULL)
098            p=t;
099        else
100            parent->data > n ? parent->l=t : parent->r=t;
101    }
102}
103 
104void tree::transverse()
105{
106    int c;
107    cout<<"\n1.InOrder\n2.Preorder\n3.Postorder\nChoice: ";
108    cin>>c;
109    switch©
110    {
111        case 1:
112            in(p);
113            break;
114 
115        case 2:
116            pre(p);
117            break;
118 
119        case 3:
120            post(p);
121            break;
122    }
123}
124 
125void tree::in(leaf *q)
126{
127    if(q!=NULL)
128    {
129        in(q->l);
130        cout<<"\t"<data<<endl;
131        in(q->r);
132    }
133     
134}
135 
136void tree::pre(leaf *q)
137{
138    if(q!=NULL)
139    {
140        cout<<"\t"<data<<endl;
141        pre(q->l);
142        pre(q->r);
143    }
144     
145}
146 
147void tree::post(leaf *q)
148{
149    if(q!=NULL)
150    {
151        post(q->l);
152        post(q->r);
153        cout<<"\t"<data<<endl;
154    }
155     
156}
157 
158void tree::findfordel(int n,int &found,leaf *&parent,leaf *&x)
159{
160    leaf *q;
161    found=0;
162    parent=NULL;
163    if(p==NULL)
164        return;
165 
166    q=p;
167    while(q!=NULL)
168    {
169        if(q->data==n)
170        {
171            found=1;
172            x=q;
173            return;
174        }
175        if(q->data>n)
176        {
177            parent=q;
178            q=q->l;
179        }
180        else
181        {
182            parent=q;
183            q=q->r;
184        }
185    }
186}
187 
188void tree::del(int num)
189{
190    leaf *parent,*x,*xsucc;
191    int found;
192 
193    // If EMPTY TREE
194    if(p==NULL)
195    {
196        cout<<"\nTree is Empty";
197        return;
198    }
199    parent=x=NULL;
200    findfordel(num,found,parent,x);
201    if(found==0)
202    {
203        cout<<"\nNode to be deleted NOT FOUND";
204        return;
205    }
206 
207    // If the node to be deleted has 2 leaves
208    if(x->l != NULL && x->r != NULL)
209    {
210        parent=x;
211        xsucc=x->r;
212 
213        while(xsucc->l != NULL)
214        {
215            parent=xsucc;
216            xsucc=xsucc->l;
217        }
218        x->data=xsucc->data;
219        x=xsucc;
220    }
221 
222    // if the node to be deleted has no child
223    if(x->l == NULL && x->r == NULL)
224    {
225        if(parent->r == x)
226            parent->r=NULL;
227        else
228            parent->l=NULL;
229 
230        delete x;
231        return;
232    }
233 
234    // if node has only right leaf
235    if(x->l == NULL && x->r != NULL )
236    {
237        if(parent->l == x)
238            parent->l=x->r;
239        else
240            parent->r=x->r;
241 
242        delete x;
243        return;
244    }
245 
246    // if node to be deleted has only left child
247    if(x->l != NULL && x->r == NULL)
248    {
249        if(parent->l == x)
250            parent->l=x->l;
251        else
252            parent->r=x->l;
253 
254        delete x;
255        return;
256    }
257}
258 
259int main()
260{
261    tree t;
262    int data[]={32,16,34,1,87,13,7,18,14,19,23,24,41,5,53};
263    for(int iter=0 ; iter < 15 ; i++)
264        t.add(data[iter]);
265 
266    t.transverse();
267    t.del(16);
268    t.transverse();
269    t.del(41);
270    t.transverse();
271    return 0;
272}


OUTPUT:
1.InOrder
2.Preorder
3.Postorder
Choice: 1
1
5
7
13
14
16
18
19
23
24
32
34
41
53
87

1.InOrder
2.Preorder
3.Postorder
Choice: 2
32
18
1
13
7
5
14
19
23
24
34
87
41
53

1.InOrder
2.Preorder
3.Postorder
Choice: 3
5
7
14
13
1
24
23
19
18
53
87
34
32
Press any key to continue


NOTE: Visual C++ may give Runtime Errors with this code. Compile with Turbo C++.

Just by looking at the output you might realise that we can print out the whole
tree in ascending order by using inorder transversal. Infact Binary Trees are
used for Searching [ Binary Search Trees {BST} ] as well as in Sorting.
The Addition of data part seems fine. Only the deletion bit needs to be
explained.

For deletion of data there are a few cases to be considered:
  • If the leaf to be deleted is not found.
  • If the leaf to be deleted has no sub-leafs.
  • If the leaf to be deleted has 1 sub-leaf.
  • If the leaf to be deleted has 2 sub-leafs.
CASE 1:
Dealing with this case is simple, we simply display an error message.

CASE 2:
Since the node has no sub-nodes, the memory occupied by this
should be freed and either the left link or the right link of the parent of this
node should be set to NULL. Which of these should be set to NULL depends upon
whether the node being deleted is a left child or a right child of its parent.

CASE 3:
In the third case we just adjust the pointer of the parent of the leaf to be
deleted such that after deletion it points to the child of the node being
deleted.

CASE 4:
The last case in which the leaf to be deleted has to sub-leaves of its own is
rather complicated.The whole logic is to locate the inorder successor, copy it's
data and reduce the problem to simple deletion of a node with one or zero leaves.
Consider in the above program...(Refer to the previous tree as well) when we are
deleting 16 we search for the next inorder successor. So we simply set the data
value to 5 and delete the node with value 5 as shown for cases 2 and 3.

That's It! *phew*
Binary Trees are used for various other things which even include
Compression algorithms,binary searching,sorting etc. A lot of Huffman,
Shannon-Fano and other Compression algorithms use Binary Trees. If you want
source code of these Compression codes you can freely contact me at my email.

X. CONTACT ME

That wraps up this Data Structure Tutorial. There are plenty of other data
structures which I'd love to mention such as Sparse Matrices, Graphs, B-Trees,
B+ Trees, AVL Trees etc. but since the aim of this tutorial was to give an
introduction to Data Structures I decided not to include them in this text.

Maybe I can save them for another Tutorial which I may write in the future.

If you have any problems in understanding the text or the source code, please
post in the forums instead of mailing me.

However, if you have any comments, suggestions or error reports, feel free to
contact me at: born2c0de AT dreamincode DOT net

*Update* : I'll be submitting a sequel to this tutorial that
discusses many more data structures very soon. Keep checking for updates.

For the downloadable text version, download the text file below.
Attached File  datastruct.txt (36.81K)


Attached image(s)

  • Resized to 100% (was 502 x 252) - Click image to enlargeAttached Image
  • Attached Image

No comments:

Post a Comment

Thank you