G
GrispernMix
//ques and and level order traversal
file name: lab6_build_leaf_up.cpp
Instructions:
1. In Lab4 you wrote the code to implement an ascending
priority queue using a linked list. In this lab using this
priority queue and a modification to your node you are going to
build a tree from the leaves up. Just as before the node for
the content of this priority queue is struct info_node. However,
we have now modified the structure to contain a character
array of size 8 instead of a field for a single character. We
have also added a father, left, and right fields. These
additional fields allow this structure to be used both in a
priority queue and also in a binary tree.
2. With your successfully implemented priority queue read the
file prq_data.txt . Using dynamic memory allocation create a
new node for each record in the prq_data.txt file. As you read
the file and create your nodes populating the content
of each node with the values from the file, insert each newly
created node into your priority queue using the value of the
weight field. Also as you create each node from dynamic memory
save the address for each node created in the array of
info_node* 's called pleaf_location[7]. This array will be used
in your next lab to start a tree climb from each of the leaf
nodes in your newly created tree.
3. After all records have been read and all nodes inserted into
your ascending priority queue, follow the following instructions:
A. Until only a single node remains in your priority queue do
the following:
a. remove two nodes at a time from your priority queue
b. using dynamic memory allocation, generate a new node and
initialize the code and weight fields. For this new
node the value of the code field will be a new code which
is the combination of the codes from the two nodes removed
from the priority queue. The value of the weight field for
this new node will be the sum of the weight fields from
the two nodes removed from the priority queue.
*** Note: Use strcat() to generate the code for the new node.
c. initialize other fields in the nodes. Initialize the father
field for the two nodes removed from the priority queue.
Initialize the left and right fields for the new node.
d. insert the new node into the ascending priority queue
B. Remove the final node from your priority queue. Assign this
node to the variable tree_root. This is the root of your tree.
4. Now write code to do a level order traversal of the tree that you
have built.
In this traversal report only the level and the codes from the tree
that occur on that level. Output from this traversal should
be sent to the file symbol_tree.txt and should appear as:
Level 0: BGCAFDE
Level 1: BGCA FDE
Level 2: BGC A FD E
..................................
Needless to say, you will have to write code to implement the
normal queue and also other code that will be used in the
level order traversal.
5. Your lab6 is now completed!!!
****NOTE*****
Due to single character input errors in Visual Studio, in your
fscanf used to read the file use a %s instead of a %c to
read the character value.
*************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define TRUE 1
#define FALSE 0
struct info_node
{
char code[8] ;
int weight ;
int level ;
struct info_node* father ;
struct info_node* left ;
struct info_node* right ;
struct info_node* next ;
} ;
struct prqueue
{
struct info_node * prqtop ;
} ;
struct lo_queue
{
struct info_node* front ;
struct info_node* rear ;
} ;
void create(struct prqueue* pq);
int empty(struct prqueue* pq);
void insert(struct prqueue* pq, struct info_node* new_node);
struct info_node* remove(struct prqueue* pq);
int oneleft(prqueue* pque);
void visit(info_node* node);
void qInsert( lo_queue* pdq, info_node* node);
int qEmpty(lo_queue* pdq);
void qCreate(struct lo_queue* pdq);
struct info_node* remove(struct prqueue* pq);
void levelOrderTraversal(lo_queue* pdq,info_node* root, int level);
void levelorder(lo_queue* pdq,info_node* root);
void main(void)
{
FILE* infile;
struct prqueue pque ;
struct lo_queue que ;
struct prqueue* pmain_queue ;
struct info_node* pleaf_location[7] ;
struct info_node* tree_root ;
struct info_node* new_node;
struct info_node* move;
struct info_node* test;
int count=0,level=0;
int numAllow = 2*level;
create(&pque);
qCreate(&que);
new_node = NULL;
test = NULL;
infile = fopen("c:/prq_data.txt", "r");
struct info_node* p1 ; // can be used in the loop which removes 2
nodes from
struct info_node* p2 ; // your priority queue
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);
test = ( struct info_node* ) malloc( sizeof ( struct info_node ) );
//fscanf(infile,"%s %d ",new_node->code,&new_node->weight);
while(!feof(infile))
{
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);
fscanf(infile,"%s%d ",new_node->code,&new_node->weight);
pleaf_location[count++] = new_node;
insert(&pque,new_node);
}
move = pque.prqtop;
// remove 2
while(!oneleft(&pque))
{
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);// create new node
p1 = ( struct info_node* ) malloc( sizeof ( struct info_node ) ); //
create node holder 1
p2 = ( struct info_node* ) malloc( sizeof ( struct info_node ) );//
create node holder 2
p1 = remove(&pque);// remove first node out of pque
p2 = remove(&pque); // remove second node out of pque
strcpy(new_node->code, p1->code);// copy new_node->code, from the
first node
strcat(new_node->code, p2->code); // copy new_node->code, from the
second node
cout << "newNode Code" << new_node->code << endl;
new_node->weight = p1->weight + p2->weight;// add the weight
together
new_node->father = new_node; // initialize the father
cout << "left p1->code = " << p1->code << endl;
cout << "right p2->code = " << p2->code << endl;
new_node->left = p1;// itialize the left
new_node->right = p2; //intialize the right
insert(&pque,new_node);//insert it into the que
}
// the last node will be the root
move = pque.prqtop;
tree_root = remove(&pque);
//tree_root = remove(&pque);
//visit(tree_root);
levelorder(&que, tree_root);
printf("End of program: ");
getch();
} // end of function main()
void create(struct prqueue* pq)
{
pq->prqtop = NULL;
}
void qCreate(lo_queue *pdq)
{
pdq->front = NULL;
pdq->rear = NULL;
}
int empty(struct prqueue* pq)
{
if(pq->prqtop == NULL)
{
return(1);
}
else
{
return(0);
}
}
void insert(struct prqueue* pq, struct info_node* new_node)
{
struct info_node* move;
struct info_node* pre_pntr;
move = pq->prqtop;
pre_pntr = pq->prqtop;
if(empty(pq))//check for empty
{
new_node->next = NULL;
pq->prqtop = new_node;
}
else
{
while(move != NULL && new_node->weight > move->weight)
{
pre_pntr = move;
move = move->next;
}
if(move == pq->prqtop)
{
new_node->next = move;
pq->prqtop = new_node;
}
else if(move == NULL)
{
new_node->next = NULL;
pre_pntr->next = new_node;
}
else
{
new_node->next = move;
pre_pntr->next = new_node;
}
}
}
struct info_node* remove(struct prqueue* pq)
{
struct info_node* remove;
remove = NULL;
if(empty(pq))
{
printf("ERROR EMPTY!!!");
}
else if(pq->prqtop->next == NULL)
{
remove = pq->prqtop;
pq->prqtop = NULL;
}
else
{
remove = pq->prqtop;
pq->prqtop = pq->prqtop->next;
}
return(remove);
//printf("%s %d\n",remove->code,remove->weight);
}
int oneleft(prqueue *pque)
{
info_node* node;
node = remove(pque);
if(empty(pque))
{
insert(pque,node);
return(1);
}
else
{
insert(pque,node);
return(0);
}
}
void visit(info_node* node)
{
if(node != NULL)
printf("%s\n", node->code) ;
}// end of function visit()
info_node* qRemove(lo_queue* pdq)
{
info_node* auxinfo;
if(qEmpty(pdq))
{
cout << "priority que empty" << endl;
}
else if(pdq->front->next == NULL)
{
auxinfo = pdq->front;
pdq->front = NULL;
pdq->rear = NULL;
}
else
{
auxinfo = pdq->front;
pdq->front = pdq->front->next;
}
return(auxinfo);
}
void qInsert(lo_queue* pdq, info_node* node )
{
if(qEmpty(pdq))
{
pdq->front = node;
pdq->rear = node;
}
else
{
pdq->rear->next = node;
pdq->rear = node;
}
}
int qEmpty(lo_queue* pdq)
{
if(pdq->front == NULL && pdq->rear == NULL)
{
return(1);
}
else
{
return(0);
}
}
void levelorder(lo_queue* pdq,info_node* root)
{
int testCounter = 0;
if(root == NULL)
cout << " ";
else{
cout << " ";
// Insert the first node
qInsert(pdq,root);
// The level we're at in the tree
int level = 0;
//cout << "level" << level << endl;
// The number of items we can take out (Binary Tree = 2 * level)
int numAllow = 2 * level;
while(!qEmpty(pdq)){
while(numAllow < 2*level)
{
info_node* temp = qRemove(pdq);
cout << temp->code << " ";
if(temp->left != NULL)
{
qInsert(pdq, temp->left);
} // end if()
if(temp->right != NULL)
{
qInsert(pdq, temp->right);
} // end if()
// We've output one of our allowed elements
numAllow++;
//cout << "numallow = " << numAllow << endl;
} // end while()
//cout << "loop" << endl;
cout << "\n ";
level++;
} // while()
cout << " ";
} // end else()
} // end breadthFirstString()
//my problem is with my level order function which keeps giving me this
error Unhandled exception //at 0x00402008 in meteor.exe: 0xC0000005:
Access violation writing location 0xbaadf029. I dont //see where i am
stepping out of my boundry, the input file is
//A 8
//B 1
//C 3
//D 5
//E 12
//F 4
//G 2
//any help would be great
file name: lab6_build_leaf_up.cpp
Instructions:
1. In Lab4 you wrote the code to implement an ascending
priority queue using a linked list. In this lab using this
priority queue and a modification to your node you are going to
build a tree from the leaves up. Just as before the node for
the content of this priority queue is struct info_node. However,
we have now modified the structure to contain a character
array of size 8 instead of a field for a single character. We
have also added a father, left, and right fields. These
additional fields allow this structure to be used both in a
priority queue and also in a binary tree.
2. With your successfully implemented priority queue read the
file prq_data.txt . Using dynamic memory allocation create a
new node for each record in the prq_data.txt file. As you read
the file and create your nodes populating the content
of each node with the values from the file, insert each newly
created node into your priority queue using the value of the
weight field. Also as you create each node from dynamic memory
save the address for each node created in the array of
info_node* 's called pleaf_location[7]. This array will be used
in your next lab to start a tree climb from each of the leaf
nodes in your newly created tree.
3. After all records have been read and all nodes inserted into
your ascending priority queue, follow the following instructions:
A. Until only a single node remains in your priority queue do
the following:
a. remove two nodes at a time from your priority queue
b. using dynamic memory allocation, generate a new node and
initialize the code and weight fields. For this new
node the value of the code field will be a new code which
is the combination of the codes from the two nodes removed
from the priority queue. The value of the weight field for
this new node will be the sum of the weight fields from
the two nodes removed from the priority queue.
*** Note: Use strcat() to generate the code for the new node.
c. initialize other fields in the nodes. Initialize the father
field for the two nodes removed from the priority queue.
Initialize the left and right fields for the new node.
d. insert the new node into the ascending priority queue
B. Remove the final node from your priority queue. Assign this
node to the variable tree_root. This is the root of your tree.
4. Now write code to do a level order traversal of the tree that you
have built.
In this traversal report only the level and the codes from the tree
that occur on that level. Output from this traversal should
be sent to the file symbol_tree.txt and should appear as:
Level 0: BGCAFDE
Level 1: BGCA FDE
Level 2: BGC A FD E
..................................
Needless to say, you will have to write code to implement the
normal queue and also other code that will be used in the
level order traversal.
5. Your lab6 is now completed!!!
****NOTE*****
Due to single character input errors in Visual Studio, in your
fscanf used to read the file use a %s instead of a %c to
read the character value.
*************
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define TRUE 1
#define FALSE 0
struct info_node
{
char code[8] ;
int weight ;
int level ;
struct info_node* father ;
struct info_node* left ;
struct info_node* right ;
struct info_node* next ;
} ;
struct prqueue
{
struct info_node * prqtop ;
} ;
struct lo_queue
{
struct info_node* front ;
struct info_node* rear ;
} ;
void create(struct prqueue* pq);
int empty(struct prqueue* pq);
void insert(struct prqueue* pq, struct info_node* new_node);
struct info_node* remove(struct prqueue* pq);
int oneleft(prqueue* pque);
void visit(info_node* node);
void qInsert( lo_queue* pdq, info_node* node);
int qEmpty(lo_queue* pdq);
void qCreate(struct lo_queue* pdq);
struct info_node* remove(struct prqueue* pq);
void levelOrderTraversal(lo_queue* pdq,info_node* root, int level);
void levelorder(lo_queue* pdq,info_node* root);
void main(void)
{
FILE* infile;
struct prqueue pque ;
struct lo_queue que ;
struct prqueue* pmain_queue ;
struct info_node* pleaf_location[7] ;
struct info_node* tree_root ;
struct info_node* new_node;
struct info_node* move;
struct info_node* test;
int count=0,level=0;
int numAllow = 2*level;
create(&pque);
qCreate(&que);
new_node = NULL;
test = NULL;
infile = fopen("c:/prq_data.txt", "r");
struct info_node* p1 ; // can be used in the loop which removes 2
nodes from
struct info_node* p2 ; // your priority queue
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);
test = ( struct info_node* ) malloc( sizeof ( struct info_node ) );
//fscanf(infile,"%s %d ",new_node->code,&new_node->weight);
while(!feof(infile))
{
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);
fscanf(infile,"%s%d ",new_node->code,&new_node->weight);
pleaf_location[count++] = new_node;
insert(&pque,new_node);
}
move = pque.prqtop;
// remove 2
while(!oneleft(&pque))
{
new_node = ( struct info_node* ) malloc( sizeof ( struct info_node )
);// create new node
p1 = ( struct info_node* ) malloc( sizeof ( struct info_node ) ); //
create node holder 1
p2 = ( struct info_node* ) malloc( sizeof ( struct info_node ) );//
create node holder 2
p1 = remove(&pque);// remove first node out of pque
p2 = remove(&pque); // remove second node out of pque
strcpy(new_node->code, p1->code);// copy new_node->code, from the
first node
strcat(new_node->code, p2->code); // copy new_node->code, from the
second node
cout << "newNode Code" << new_node->code << endl;
new_node->weight = p1->weight + p2->weight;// add the weight
together
new_node->father = new_node; // initialize the father
cout << "left p1->code = " << p1->code << endl;
cout << "right p2->code = " << p2->code << endl;
new_node->left = p1;// itialize the left
new_node->right = p2; //intialize the right
insert(&pque,new_node);//insert it into the que
}
// the last node will be the root
move = pque.prqtop;
tree_root = remove(&pque);
//tree_root = remove(&pque);
//visit(tree_root);
levelorder(&que, tree_root);
printf("End of program: ");
getch();
} // end of function main()
void create(struct prqueue* pq)
{
pq->prqtop = NULL;
}
void qCreate(lo_queue *pdq)
{
pdq->front = NULL;
pdq->rear = NULL;
}
int empty(struct prqueue* pq)
{
if(pq->prqtop == NULL)
{
return(1);
}
else
{
return(0);
}
}
void insert(struct prqueue* pq, struct info_node* new_node)
{
struct info_node* move;
struct info_node* pre_pntr;
move = pq->prqtop;
pre_pntr = pq->prqtop;
if(empty(pq))//check for empty
{
new_node->next = NULL;
pq->prqtop = new_node;
}
else
{
while(move != NULL && new_node->weight > move->weight)
{
pre_pntr = move;
move = move->next;
}
if(move == pq->prqtop)
{
new_node->next = move;
pq->prqtop = new_node;
}
else if(move == NULL)
{
new_node->next = NULL;
pre_pntr->next = new_node;
}
else
{
new_node->next = move;
pre_pntr->next = new_node;
}
}
}
struct info_node* remove(struct prqueue* pq)
{
struct info_node* remove;
remove = NULL;
if(empty(pq))
{
printf("ERROR EMPTY!!!");
}
else if(pq->prqtop->next == NULL)
{
remove = pq->prqtop;
pq->prqtop = NULL;
}
else
{
remove = pq->prqtop;
pq->prqtop = pq->prqtop->next;
}
return(remove);
//printf("%s %d\n",remove->code,remove->weight);
}
int oneleft(prqueue *pque)
{
info_node* node;
node = remove(pque);
if(empty(pque))
{
insert(pque,node);
return(1);
}
else
{
insert(pque,node);
return(0);
}
}
void visit(info_node* node)
{
if(node != NULL)
printf("%s\n", node->code) ;
}// end of function visit()
info_node* qRemove(lo_queue* pdq)
{
info_node* auxinfo;
if(qEmpty(pdq))
{
cout << "priority que empty" << endl;
}
else if(pdq->front->next == NULL)
{
auxinfo = pdq->front;
pdq->front = NULL;
pdq->rear = NULL;
}
else
{
auxinfo = pdq->front;
pdq->front = pdq->front->next;
}
return(auxinfo);
}
void qInsert(lo_queue* pdq, info_node* node )
{
if(qEmpty(pdq))
{
pdq->front = node;
pdq->rear = node;
}
else
{
pdq->rear->next = node;
pdq->rear = node;
}
}
int qEmpty(lo_queue* pdq)
{
if(pdq->front == NULL && pdq->rear == NULL)
{
return(1);
}
else
{
return(0);
}
}
void levelorder(lo_queue* pdq,info_node* root)
{
int testCounter = 0;
if(root == NULL)
cout << " ";
else{
cout << " ";
// Insert the first node
qInsert(pdq,root);
// The level we're at in the tree
int level = 0;
//cout << "level" << level << endl;
// The number of items we can take out (Binary Tree = 2 * level)
int numAllow = 2 * level;
while(!qEmpty(pdq)){
while(numAllow < 2*level)
{
info_node* temp = qRemove(pdq);
cout << temp->code << " ";
if(temp->left != NULL)
{
qInsert(pdq, temp->left);
} // end if()
if(temp->right != NULL)
{
qInsert(pdq, temp->right);
} // end if()
// We've output one of our allowed elements
numAllow++;
//cout << "numallow = " << numAllow << endl;
} // end while()
//cout << "loop" << endl;
cout << "\n ";
level++;
} // while()
cout << " ";
} // end else()
} // end breadthFirstString()
//my problem is with my level order function which keeps giving me this
error Unhandled exception //at 0x00402008 in meteor.exe: 0xC0000005:
Access violation writing location 0xbaadf029. I dont //see where i am
stepping out of my boundry, the input file is
//A 8
//B 1
//C 3
//D 5
//E 12
//F 4
//G 2
//any help would be great