Identify data structure
Data structure
- Elementary items constitute a unit and that unit may be considered as a structure.
- Data structure is a structure or unit where we organize elementary data items in different ways.
- Usually elementary data items are the elements of a data structure.
- However, a data structure may be an element of another data structure. That means a data structure may contain another data structure.
pre-paid card system
#include"stdio.h"
#includeint main(void)
{
int n,pcn=12345;
printf("Enter your pre-paid card number : ");
scanf("%d",&n);
if(n==pcn)
{
printf("your balance is : 300 BDT\n\n");
}
else if(n!=pcn)
{
printf("Enter your pre-paid card number Again : ");
scanf("%d",&n);
if(n==pcn)
{
printf("your balance is : 300 BDT\n\n");
}
if(n!=pcn)
{
printf("Enter your pre-paid card number Again : ");
scanf("%d",&n);
if(n==pcn)
{
printf("your balance is : 300 BDT\n\n");
}
else
{
printf("\nyour card number is invalid!!!!\n\nYou can insert card number After 6 Hours\n\n");
}
}
}
return 0;
}
student class tests
#include"stdio.h"
#include"conio.h"
void main()
{
int marks[40][4];
float avg_mrk[4];
int sum,min_mrk;
printf("Enter class test marks: \n");
for(int i=0;i<40;++i)
{
printf("serial No %d :\n",i+1);
for(int j=0;j<4;j++)
{
scanf("%d",&marks[i][j]);
}
sum=0;
min_mrk=marks[i][0];
for(j=0;j<4;j++)
{
sum=sum+marks[i][j];
if(min_mrk>marks[i][j])
min_mrk=marks[i][j];
}
avg_mrk[i]=float(sum-min_mrk)/3;
}
printf("Average marks : \n");
for(i=0;i<40;i++)
{
printf("serial No %d :\t",i+1);
printf("%.2f: \n ",avg_mrk[i]);
}
}
/* OUTPUT
Enter class test marks:
serial No 1 :
17 18 19 17
serial No 2 :
18 18 19 17
serial No 3 :
18 16 15 13
serial No 4 :
10 08 19 20
..........
serial No 40 :
18 18 19 17
Average marks :
serial No 1 : 18.00:
serial No 2 : 18.33:
serial No 3 : 16.33:
serial No 4 : 16.33:
..................
serial No 40 : 18.33:
*/
#include"conio.h"
void main()
{
int marks[40][4];
float avg_mrk[4];
int sum,min_mrk;
printf("Enter class test marks: \n");
for(int i=0;i<40;++i)
{
printf("serial No %d :\n",i+1);
for(int j=0;j<4;j++)
{
scanf("%d",&marks[i][j]);
}
sum=0;
min_mrk=marks[i][0];
for(j=0;j<4;j++)
{
sum=sum+marks[i][j];
if(min_mrk>marks[i][j])
min_mrk=marks[i][j];
}
avg_mrk[i]=float(sum-min_mrk)/3;
}
printf("Average marks : \n");
for(i=0;i<40;i++)
{
printf("serial No %d :\t",i+1);
printf("%.2f: \n ",avg_mrk[i]);
}
}
/* OUTPUT
Enter class test marks:
serial No 1 :
17 18 19 17
serial No 2 :
18 18 19 17
serial No 3 :
18 16 15 13
serial No 4 :
10 08 19 20
..........
serial No 40 :
18 18 19 17
Average marks :
serial No 1 : 18.00:
serial No 2 : 18.33:
serial No 3 : 16.33:
serial No 4 : 16.33:
..................
serial No 40 : 18.33:
*/
Arrange in link list
#include"stdio.h"
#include"iostream.h>
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void sort(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<data;
curptr=curptr->next;
}
//cout<<" "<data;
}
void linklist::sort(int item)
{
node *pptr,*fptr;
pptr=list;
while(pptr !=NULL)
{
fptr=pptr->next;
while(fptr !=NULL)
{
if(pptr->data>fptr->data)
{
int temp;
temp=pptr->data;
pptr->data=fptr->data;
fptr->data=temp;
}
fptr=fptr->next;
}
pptr=pptr->next;
}
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :";
mylist.showdata();
//mylist.sort();
//char ans;
/* cout<<"\nDo you want to sort the list ?(y for yes )\t";
cin>>ans;
if(ans=='y'|| ans=='Y')
{
//int x;
//cout<<"\n\n Enter the node value to be deleted: ";
//cin>>x;*/
mylist.sort(d);
cout<<"\n\nsort Data in the list: \t";
mylist.showdata();
cout<<"\n";
return 0;
}
#include"iostream.h>
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void sort(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<
curptr=curptr->next;
}
//cout<<" "<
}
void linklist::sort(int item)
{
node *pptr,*fptr;
pptr=list;
while(pptr !=NULL)
{
fptr=pptr->next;
while(fptr !=NULL)
{
if(pptr->data>fptr->data)
{
int temp;
temp=pptr->data;
pptr->data=fptr->data;
fptr->data=temp;
}
fptr=fptr->next;
}
pptr=pptr->next;
}
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :";
mylist.showdata();
//mylist.sort();
//char ans;
/* cout<<"\nDo you want to sort the list ?(y for yes )\t";
cin>>ans;
if(ans=='y'|| ans=='Y')
{
//int x;
//cout<<"\n\n Enter the node value to be deleted: ";
//cin>>x;*/
mylist.sort(d);
cout<<"\n\nsort Data in the list: \t";
mylist.showdata();
cout<<"\n";
return 0;
}
double_link_list
#include"stdio.h"
#include"iostream.h"
#include"conio.h"
struct node
{
node *pre;
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode (int item);
void link(); //constructed
void showdata();
};
void linklist::newnode(int item)
{
nptr=new(node);
nptr->pre=NULL;
nptr->data=item;
nptr->next=NULL;
link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
nptr->pre=tptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr =list;
while(curptr->next !=NULL)
{
cout<<" " <data;
curptr=curptr->next;
}
cout<<" " <data;
//curptr=curptr-next
}
int main()
{
int n,d;
linklist mylist;
cout<<"how many node do you have?\t";
cin>>n;
cout<<"Enter data:"<<"\n";
for(int i=0;i
cin>>d;
mylist.newnode(d);
}
cout<<"data in the list:";
mylist.showdata();
return 0;
}
#include"iostream.h"
#include"conio.h"
struct node
{
node *pre;
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode (int item);
void link(); //constructed
void showdata();
};
void linklist::newnode(int item)
{
nptr=new(node);
nptr->pre=NULL;
nptr->data=item;
nptr->next=NULL;
link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
nptr->pre=tptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr =list;
while(curptr->next !=NULL)
{
cout<<" " <
curptr=curptr->next;
}
cout<<" " <
//curptr=curptr-next
}
int main()
{
int n,d;
linklist mylist;
cout<<"how many node do you have?\t";
cin>>n;
cout<<"Enter data:"<<"\n";
for(int i=0;i
cin>>d;
mylist.newnode(d);
}
cout<<"data in the list:";
mylist.showdata();
return 0;
}
deleting in link list
#include 'stdio.h'
#include 'iostream.h'
#include 'conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void deletion(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<data;
curptr=curptr->next;
}
//cout<<" "<data;
}
void linklist::deletion(int item)
{
node *pptr;
tptr=list;
if(list->data!=item)
{
while(tptr->data!=item)
{
if(tptr==NULL)
{
cout<<"\nItem is not found in the list\n";
break;
}
pptr=tptr;
tptr=tptr->next;
}
pptr->next=tptr->next;
delete(tptr);
}
else
{
list =list->next;
delete(tptr);
}
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :";
mylist.showdata();
char ans;
cout<<"\nDo you want to delete a node ?(y for yes )\t";
cin>>ans;
if(ans=='y'|| ans=='Y')
{
int x;
cout<<"\n\n Enter the node value to be deleted: ";
cin>>x;
mylist.deletion(x);
cout<
mylist.showdata();
cout<<"\n";
}
return 0;
}
#include 'iostream.h'
#include 'conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void deletion(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<
curptr=curptr->next;
}
//cout<<" "<
}
void linklist::deletion(int item)
{
node *pptr;
tptr=list;
if(list->data!=item)
{
while(tptr->data!=item)
{
if(tptr==NULL)
{
cout<<"\nItem is not found in the list\n";
break;
}
pptr=tptr;
tptr=tptr->next;
}
pptr->next=tptr->next;
delete(tptr);
}
else
{
list =list->next;
delete(tptr);
}
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :";
mylist.showdata();
char ans;
cout<<"\nDo you want to delete a node ?(y for yes )\t";
cin>>ans;
if(ans=='y'|| ans=='Y')
{
int x;
cout<<"\n\n Enter the node value to be deleted: ";
cin>>x;
mylist.deletion(x);
cout<
mylist.showdata();
cout<<"\n";
}
return 0;
}
search link list
#include"stdio.h"
#include"iostream.h"
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void search(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::search(int item)
{
tptr=list;
while(tptr !=NULL)
{
if(tptr->data==item)
{
cout<<"Data Found !\n"; break; } tptr=tptr->next;
if(tptr==NULL)
cout<<"Data is not in the list\n"; } } void linklist::showdata() { node *curptr; curptr=list; while(curptr !=NULL) { cout<<" "<data;
curptr=curptr->next;
}
//cout<<" "<data;
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t"; cin>>n;
cout<<"\n Enter data for nodes :"; for(int i=0;i>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :"; mylist.showdata(); int item; cout<<"\n Enter the data to be found: "; cin>>item;
cout<<"\n Search Result: ";
mylist.search(item);
return 0;
}
http://www.google.com.bd/search?q=search+link+list&pov=100366784536684831572&usg=__l-bqafYvVrd4O1wVprEd-7Upvu0=&hl=en
#include"iostream.h"
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
void search(int item);
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::search(int item)
{
tptr=list;
while(tptr !=NULL)
{
if(tptr->data==item)
{
cout<<"Data Found !\n"; break; } tptr=tptr->next;
if(tptr==NULL)
cout<<"Data is not in the list\n"; } } void linklist::showdata() { node *curptr; curptr=list; while(curptr !=NULL) { cout<<" "<
curptr=curptr->next;
}
//cout<<" "<
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t"; cin>>n;
cout<<"\n Enter data for nodes :"; for(int i=0;i
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list :"; mylist.showdata(); int item; cout<<"\n Enter the data to be found: "; cin>>item;
cout<<"\n Search Result: ";
mylist.search(item);
return 0;
}
http://www.google.com.bd/search?q=search+link+list&pov=100366784536684831572&usg=__l-bqafYvVrd4O1wVprEd-7Upvu0=&hl=en
Link list creation
#include"stdio.h"
#include"iostream.h"
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<data;
curptr=curptr->next;
}
//cout<<" "<data;
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list : ";
mylist.showdata();
cout<<"\n";
// getch();
return 0;
}
#include"iostream.h"
#include"conio.h"
struct node
{
int data;
node *next;
};
class linklist
{
node *list,*nptr,*tptr;
public:
linklist()
{
list=NULL;
}
void newnode(int item);
void link();
void showdata();
};
void linklist::newnode(int item)
{
nptr =new(node);
nptr->data=item;
nptr->next=NULL;
//link();
}
void linklist::link()
{
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
void linklist::showdata()
{
node *curptr;
curptr=list;
while(curptr !=NULL)
{
cout<<" "<
curptr=curptr->next;
}
//cout<<" "<
}
int main()
{
int n,d;
linklist mylist;
cout<<"\n How many nodes you have ?\t";
cin>>n;
cout<<"\n Enter data for nodes :";
for(int i=0;i
cin>>d;
mylist.newnode(d);
mylist.link();
}
cout<<"data in the list : ";
mylist.showdata();
cout<<"\n";
// getch();
return 0;
}
largest Element in the array
Back
#include "stdio.h"
#include "conio.h"
void main()
{
int a[15],lar,I,n,odd,even;
printf("Enter the size of the array\n");
scanf("%d",&n);
printf("Enter the elements of the array\n");
for(I=0;Ilar)
lar=a[I];
}
printf("\n%d is largest Element in the array\n\n",lar);
for(I=0;I
{
if(a[I]%2!=0)
{
odd=a[I];
printf("%d : ",odd);
}
}
printf("are odd number \n\n");
for(I=0;I
{
if(a[I]%2==0)
{
even=a[I];
printf("%d : ",I);
}
}
printf("Even number position \n\n");
for(I=0;I
{
if(a[I]%2==0)
{
even=a[I];
printf("%d : ",even);
}
}
printf("are even number \n\n");
}
#include "stdio.h"
#include "conio.h"
void main()
{
int a[15],lar,I,n,odd,even;
printf("Enter the size of the array\n");
scanf("%d",&n);
printf("Enter the elements of the array\n");
for(I=0;I
lar=a[I];
}
printf("\n%d is largest Element in the array\n\n",lar);
for(I=0;I
{
if(a[I]%2!=0)
{
odd=a[I];
printf("%d : ",odd);
}
}
printf("are odd number \n\n");
for(I=0;I
{
if(a[I]%2==0)
{
even=a[I];
printf("%d : ",I);
}
}
printf("Even number position \n\n");
for(I=0;I
{
if(a[I]%2==0)
{
even=a[I];
printf("%d : ",even);
}
}
printf("are even number \n\n");
}
leap year in c
include stdio.h
int main(void)
{
int n;
printf("enter year (like this 2005) :");
scanf("%d",&n);
if(n%4==0 && n%100 !=0 || n%400==0)
printf("%d is leap year \n",n);
else
printf("%d is not leap year\n ",n);
return 0;
}
int main(void)
{
int n;
printf("enter year (like this 2005) :");
scanf("%d",&n);
if(n%4==0 && n%100 !=0 || n%400==0)
printf("%d is leap year \n",n);
else
printf("%d is not leap year\n ",n);
return 0;
}
Basic binary search tree routines
Back
//Basic binary search tree routines
#include stdio.h
#include stdlib.h
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
/* insert, swap, search value, search minimum and search maximum values */
struct tnode *tnode_insert(struct tnode *p, int value);
struct tnode *tnode_swap(struct tnode *p);
struct tnode *tnode_search(struct tnode *p, int key);
struct tnode *tnode_searchmin(struct tnode *p);
struct tnode *tnode_searchmax(struct tnode *p);
/* destroy, count tree nodes */
void tnode_destroy(struct tnode *p);
int tnode_count(struct tnode *p);
/* print binary tree inorder, preorder, postorder [recursive] */
void print_inorder(struct tnode *p);
void print_preorder(struct tnode *p);
void print_postorder(struct tnode *p);
int main(void) {
int demo_nr[] = {1, 3, 4, 7, 2, 9, 9, 0, 5, 6, 8, 7, 1, 2, 4};
struct tnode *root = NULL;
struct tnode *searchval = NULL;
int querry = 0;
int i = 0;
/* demo: insert some nr's into the binary tree */
for(i = 0; i < 15; i++)
root = tnode_insert(root, demo_nr[i]);
printf("=-=-=\n");
printf("Total number of tree nodes: %d\n", tnode_count(root));
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Enter integer, find: ");
scanf("%d", &querry);
searchval = tnode_search(root, querry);
if(searchval == NULL)
printf(" * %d Not! found in btree\n", querry);
else
printf(" * Found! %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Minimum value\n");
searchval = tnode_searchmin(root);
if(searchval == NULL)
printf(" * Minimum Not! found in btree ?\n");
else
printf(" * Found! minimum value %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Maximum value\n");
searchval = tnode_searchmax(root);
if(searchval == NULL)
printf(" * Maximum Not! found in btree ?\n");
else
printf(" * Found! Maximum value %d in btree\n", searchval->data);
printf("=-=-=\n");
printf("Exchanging all tree nodes: left <-> right\n");
root = tnode_swap(root);
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Destroying btree... bye!\n");
tnode_destroy(root);
return 0;
}
/* insert a tnode into the binary tree */
struct tnode *tnode_insert(struct tnode *p, int value) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p == NULL) {
/* insert [new] tnode as root node */
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = value;
p->left = p->right = NULL;
} else {
tmp_one = p;
/* Traverse the tree to get a pointer to the specific tnode */
/* The child of this tnode will be the [new] tnode */
while(tmp_one != NULL) {
tmp_two = tmp_one;
if(tmp_one ->data > value)
tmp_one = tmp_one->left;
else
tmp_one = tmp_one->right;
}
if(tmp_two->data > value) {
/* insert [new] tnode as left child */
tmp_two->left = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->left;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
} else {
/* insert [new] tnode as left child */
tmp_two->right = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->right;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
}
}
return(p);
}
/* print binary tree inorder */
void print_inorder(struct tnode *p) {
if(p != NULL) {
print_inorder(p->left);
printf("%d ", p->data);
print_inorder(p->right);
}
}
/* print binary tree preorder */
void print_preorder(struct tnode *p) {
if(p != NULL) {
printf("%d ", p->data);
print_preorder(p->left);
print_preorder(p->right);
}
}
/* print binary tree postorder */
void print_postorder(struct tnode *p) {
if(p != NULL) {
print_postorder(p->left);
print_postorder(p->right);
printf("%d ", p->data);
}
}
/* returns the total number of tree nodes */
int tnode_count(struct tnode *p) {
if(p == NULL)
return 0;
else {
if(p->left == NULL && p->right == NULL)
return 1;
else
return(1 + (tnode_count(p->left) + tnode_count(p->right)));
}
}
/* exchange all left and right tnodes */
struct tnode *tnode_swap(struct tnode *p) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p != NULL) {
tmp_one = tnode_swap(p->left);
tmp_two = tnode_swap(p->right);
p->right = tmp_one;
p->left = tmp_two;
}
return(p);
}
/* locate a value in the btree */
struct tnode *tnode_search(struct tnode *p, int key) {
struct tnode *temp;
temp = p;
while(temp != NULL) {
if(temp->data == key)
return temp;
else if(temp->data > key)
temp = temp->left;
else
temp = temp->right;
}
return NULL;
}
/* locate a minimum value in the btree */
struct tnode *tnode_searchmin(struct tnode *p) {
if(p == NULL)
return NULL;
else
if(p->left == NULL)
return p;
else
return tnode_searchmin(p->left);
}
/* locate a maximum value in the btree */
struct tnode *tnode_searchmax(struct tnode *p) {
if(p != NULL)
while(p->right != NULL)
p = p->right;
return p;
}
/* destroy the binary tree */
void tnode_destroy(struct tnode *p) {
if(p != NULL) {
tnode_destroy(p->left);
tnode_destroy(p->right);
free(p);
}
}
//Basic binary search tree routines
#include stdio.h
#include stdlib.h
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
/* insert, swap, search value, search minimum and search maximum values */
struct tnode *tnode_insert(struct tnode *p, int value);
struct tnode *tnode_swap(struct tnode *p);
struct tnode *tnode_search(struct tnode *p, int key);
struct tnode *tnode_searchmin(struct tnode *p);
struct tnode *tnode_searchmax(struct tnode *p);
/* destroy, count tree nodes */
void tnode_destroy(struct tnode *p);
int tnode_count(struct tnode *p);
/* print binary tree inorder, preorder, postorder [recursive] */
void print_inorder(struct tnode *p);
void print_preorder(struct tnode *p);
void print_postorder(struct tnode *p);
int main(void) {
int demo_nr[] = {1, 3, 4, 7, 2, 9, 9, 0, 5, 6, 8, 7, 1, 2, 4};
struct tnode *root = NULL;
struct tnode *searchval = NULL;
int querry = 0;
int i = 0;
/* demo: insert some nr's into the binary tree */
for(i = 0; i < 15; i++)
root = tnode_insert(root, demo_nr[i]);
printf("=-=-=\n");
printf("Total number of tree nodes: %d\n", tnode_count(root));
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Enter integer, find: ");
scanf("%d", &querry);
searchval = tnode_search(root, querry);
if(searchval == NULL)
printf(" * %d Not! found in btree\n", querry);
else
printf(" * Found! %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Minimum value\n");
searchval = tnode_searchmin(root);
if(searchval == NULL)
printf(" * Minimum Not! found in btree ?\n");
else
printf(" * Found! minimum value %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Maximum value\n");
searchval = tnode_searchmax(root);
if(searchval == NULL)
printf(" * Maximum Not! found in btree ?\n");
else
printf(" * Found! Maximum value %d in btree\n", searchval->data);
printf("=-=-=\n");
printf("Exchanging all tree nodes: left <-> right\n");
root = tnode_swap(root);
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Destroying btree... bye!\n");
tnode_destroy(root);
return 0;
}
/* insert a tnode into the binary tree */
struct tnode *tnode_insert(struct tnode *p, int value) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p == NULL) {
/* insert [new] tnode as root node */
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = value;
p->left = p->right = NULL;
} else {
tmp_one = p;
/* Traverse the tree to get a pointer to the specific tnode */
/* The child of this tnode will be the [new] tnode */
while(tmp_one != NULL) {
tmp_two = tmp_one;
if(tmp_one ->data > value)
tmp_one = tmp_one->left;
else
tmp_one = tmp_one->right;
}
if(tmp_two->data > value) {
/* insert [new] tnode as left child */
tmp_two->left = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->left;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
} else {
/* insert [new] tnode as left child */
tmp_two->right = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->right;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
}
}
return(p);
}
/* print binary tree inorder */
void print_inorder(struct tnode *p) {
if(p != NULL) {
print_inorder(p->left);
printf("%d ", p->data);
print_inorder(p->right);
}
}
/* print binary tree preorder */
void print_preorder(struct tnode *p) {
if(p != NULL) {
printf("%d ", p->data);
print_preorder(p->left);
print_preorder(p->right);
}
}
/* print binary tree postorder */
void print_postorder(struct tnode *p) {
if(p != NULL) {
print_postorder(p->left);
print_postorder(p->right);
printf("%d ", p->data);
}
}
/* returns the total number of tree nodes */
int tnode_count(struct tnode *p) {
if(p == NULL)
return 0;
else {
if(p->left == NULL && p->right == NULL)
return 1;
else
return(1 + (tnode_count(p->left) + tnode_count(p->right)));
}
}
/* exchange all left and right tnodes */
struct tnode *tnode_swap(struct tnode *p) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p != NULL) {
tmp_one = tnode_swap(p->left);
tmp_two = tnode_swap(p->right);
p->right = tmp_one;
p->left = tmp_two;
}
return(p);
}
/* locate a value in the btree */
struct tnode *tnode_search(struct tnode *p, int key) {
struct tnode *temp;
temp = p;
while(temp != NULL) {
if(temp->data == key)
return temp;
else if(temp->data > key)
temp = temp->left;
else
temp = temp->right;
}
return NULL;
}
/* locate a minimum value in the btree */
struct tnode *tnode_searchmin(struct tnode *p) {
if(p == NULL)
return NULL;
else
if(p->left == NULL)
return p;
else
return tnode_searchmin(p->left);
}
/* locate a maximum value in the btree */
struct tnode *tnode_searchmax(struct tnode *p) {
if(p != NULL)
while(p->right != NULL)
p = p->right;
return p;
}
/* destroy the binary tree */
void tnode_destroy(struct tnode *p) {
if(p != NULL) {
tnode_destroy(p->left);
tnode_destroy(p->right);
free(p);
}
}
Subscribe to:
Posts (Atom)