How do I do it? It's simple finding nodes and adding new nodes, but how does one list all nodes? I'd prefer to do it without recursion, although I realize that that's a popular method. Also, a question about deleting nodes. My method was to make the previous node's left and right links equal to the target node's left and right links, then deleting the target node. What if the previous one has left and right links filled and so does the target? One link either left or right will be fine, BUT, there will be a lost link. How does one get around this? Simply adding a third misc. link won't do in the event of multiple deletes of this style. Thx in advance.
Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Listing all nodes in a 'Tree'
- Thread starter Chemakill
- Start date
- Thread starter
- #2
Okay, the delete function has been solved. But the question remains; how to list all nodes in a tree without recursion?
The following is my code. It gets exactly six illegal escape sequence errors that I do not understand. And yes, this IS high school programming class, but we were told to figure it out by any means, books, Internet and tech forums allowed. So don't let guilt stop you from helping.
As well, non working functions (in progress) are commented out.
//Ryan's Employee program, Tree Version.
/* Progress
Complete:
main
add
listind
delete
In Progress:
listall
payroll
*/
#include <stdio.h>
//The structure
struct EmployeeRecord
{
long empnum;
char name[25];
short pc;
float sal;
//left is a pointer that points to the record to the left (Lesser than the first record)
EmployeeRecord *left;
//right is a pointer that points to the record to the right (Greater than the first record)
EmployeeRecord *right;
};
typedef struct EmployeeRecord SER;
//These are the pointers which will create and traverse the link list.
//The ptr_add can never change outside of add or it will warp the list.
//The ptr_top must always show the last record.
//The root must always equal NULL and represent the beginning of the list.
SER *ptr_head, *ptr_temp;
//flag determines if a record has ever been added.
short flag = 0;
void menu();
void add();
void listind();
void listall();
void delet();
void payroll();
void main()
{
//Set the initial values of all the pointers.
//Create the first record and equate the links to NULL
ptr_head = new EmployeeRecord;
//Assign the arbitrary value to the first record, as it should not be used for real records,
//since it can not be deleted.
ptr_head->empnum = 5000;
ptr_head->right=NULL;
ptr_head->left=NULL;
menu();
printf("This program written by Ryan McPherson.\n"
;
}
void menu()
{
short choice;
//The menu loop
do
{
printf("Menu\n\n"
printf("1. Add a record.\n2. List a record.\n3. List all records\n"
printf("4. Delete a record.\n5. Calculate total payroll.\n6. Exit\n"
printf("\nYour choice: "
scanf("%d", &choice);
switch(choice)
{
case 1: add();
break;
case 2: listind();
break;
case 3: listall();
break;
case 4: delet();
break;
case 5: payroll();
break;
case 6: break;
default: printf("Please select a valid option.\n"
menu();
break;
}
}
while(choice < 6);
}
void add()
{
short x, ct, emptemp;
printf("How many records would you like to add?\n"
scanf("%d", &x);
//Loop the correct number of times
for(ct = 0; ct<x; ct++)
{
//Set the adding pointer to the beginning (ptr_head) of the tree structure
ptr_temp = ptr_head;
//Get a temporary empnum to determine location of the new record.
printf("Please enter the employee number.\n"
scanf("%d", &emptemp);
//Find the location of the new record
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//If the temporary empnum is greater than the current, and the
//right link isn't null, move right.
if(emptemp > ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_temp=ptr_temp->right;
}
//If the temporary empnum is lower than the current, and the
//left link isn't null, move left.
if(emptemp<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_temp=ptr_temp->left;
}
}
//If the temporary empnum is lower than the current,
if(emptemp < ptr_temp->empnum)
{
//Create a new record on the left. Point to it.
ptr_temp->left = new SER;
ptr_temp = ptr_temp->left;
}
else
{
//Otherwise it's higher than the current.
//Create a new record on the right. Point to it.
ptr_temp->right = new SER;
ptr_temp = ptr_temp->right;
}
//Finally we point to the new record in it's proper position, so we can store the
//temporary employee number.
ptr_temp->empnum = emptemp;
//Store the rest of the data.
printf("Please enter the employee's name.\n"
scanf("%s", ptr_temp->name);
printf("Please enter the employee's pay code.\n"
scanf("%d", &ptr_temp->pc);
printf("Please enter the employee's salary.\n"
scanf("%f", &ptr_temp->sal);
ptr_temp->left = NULL;
ptr_temp->right = NULL;
}
printf("\n\n\n"
}
void listind()
{
//This is a the choice variable and a flag.
short choice;
//Get an employee number to determine location of the record to be printed.
printf("Please enter the employee number.\n"
scanf("%d", &choice);
//Set the temporary pointer to the top of the tree.
ptr_temp = ptr_head;
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//If the employee number is greater than the current, and the
//right link isn't null, move right.
if(choice>ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_temp=ptr_temp->right;
}
//If the employee number is lower than the current, and the
//left link isn't null, move left.
if(choice<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_temp=ptr_temp->left;
}
}
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
printf("\n\n\n"
}
void listall()
{
/*
//Set the temp pointer to the top of the tree.
ptr_temp = ptr_head;
//Loops and prints
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//Print the current record
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
//Advance down the tree
}
printf("\n\n\n"
*/
}
void delet()
{
short choice, lrflag=3;
char confirm = 'n';
SER *ptr_saved, *ptr_del;
printf("Please enter the employee number of the employee you would like to delete.\n"
scanf("%d", &choice);
//Set the temporary pointer to the top of the tree.
ptr_temp = ptr_head;
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL && ptr_temp->empnum!=choice)
{
//If the employee number is greater than the current, and the
//right link isn't null, move right.
//lrflag will tell us whether the last move was from a left or right link.
if(choice>ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_saved=ptr_temp;
ptr_temp=ptr_temp->right;
lrflag=2;
}
//If the employee number is lower than the current, and the
//left link isn't null, move left.
if(choice<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_saved=ptr_temp;
ptr_temp=ptr_temp->left;
lrflag=1;
}
}
//For once, we DON'T have to worry about the first record.
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
printf("Are you sure you wish to delete this record? (y/n): "
getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
if(ptr_saved->left!=NULL && ptr_saved->right!=NULL && ptr_temp->left!=NULL && ptr_temp->right!=NULL)
{
if(lrflag == 1)
{
ptr_del = ptr_saved;
ptr_del = ptr_del->right;
while(ptr_del->left!=NULL && ptr_del->right!=NULL)
{
ptr_del = ptr_del->left;
}
ptr_del->left = ptr_temp->left;
ptr_del->right = ptr_temp->right;
}
if(lrflag == 2)
{
ptr_del = ptr_saved;
ptr_del = ptr_del->left;
while(ptr_del->left!=NULL && ptr_del->right!=NULL)
{
ptr_del = ptr_del->right;
}
ptr_del->left = ptr_temp->left;
ptr_del->right = ptr_del->right;
}
}
else
{
if(ptr_temp->left!=NULL && lrflag == 1 || ptr_temp->left!=NULL && ptr_saved->left==NULL)
{
ptr_saved->left = ptr_temp->left;
}
if(ptr_temp->right!=NULL && lrflag == 2 || ptr_temp->right!=NULL && ptr_saved->right==NULL)
{
ptr_saved->right = ptr_temp->right;
}
}
delete ptr_temp;
printf("Record deleted.\n"
}
printf("\n\n\n"
}
void payroll()
{
/* double tpay = 0;
short pc1=8*5*52, pc2=5*52;
//Set the temp pointer to the top
ptr_temp = ptr_top;
//loops, calculates a value.
do
{
switch(ptr_temp->pc)
{
case 1: tpay = tpay + ptr_temp->sal*pc1;
break;
case 2: tpay = tpay + ptr_temp->sal*pc2;
break;
case 3: tpay = tpay + ptr_temp->sal*52;
break;
case 4: tpay = tpay + ptr_temp->sal*26;
break;
default: break;
}
//Advance onward!
ptr_temp = ptr_temp->link;
}
//Until we hit the fence.
while(ptr_temp != NULL);
printf("The total payroll is: $%7.2f\n\n\n", tpay);
*/
}
The following is my code. It gets exactly six illegal escape sequence errors that I do not understand. And yes, this IS high school programming class, but we were told to figure it out by any means, books, Internet and tech forums allowed. So don't let guilt stop you from helping.
As well, non working functions (in progress) are commented out.
//Ryan's Employee program, Tree Version.
/* Progress
Complete:
main
add
listind
delete
In Progress:
listall
payroll
*/
#include <stdio.h>
//The structure
struct EmployeeRecord
{
long empnum;
char name[25];
short pc;
float sal;
//left is a pointer that points to the record to the left (Lesser than the first record)
EmployeeRecord *left;
//right is a pointer that points to the record to the right (Greater than the first record)
EmployeeRecord *right;
};
typedef struct EmployeeRecord SER;
//These are the pointers which will create and traverse the link list.
//The ptr_add can never change outside of add or it will warp the list.
//The ptr_top must always show the last record.
//The root must always equal NULL and represent the beginning of the list.
SER *ptr_head, *ptr_temp;
//flag determines if a record has ever been added.
short flag = 0;
void menu();
void add();
void listind();
void listall();
void delet();
void payroll();
void main()
{
//Set the initial values of all the pointers.
//Create the first record and equate the links to NULL
ptr_head = new EmployeeRecord;
//Assign the arbitrary value to the first record, as it should not be used for real records,
//since it can not be deleted.
ptr_head->empnum = 5000;
ptr_head->right=NULL;
ptr_head->left=NULL;
menu();
printf("This program written by Ryan McPherson.\n"
;}
void menu()
{
short choice;
//The menu loop
do
{
printf("Menu\n\n"
;printf("1. Add a record.\n2. List a record.\n3. List all records\n"
;printf("4. Delete a record.\n5. Calculate total payroll.\n6. Exit\n"
;printf("\nYour choice: "
;scanf("%d", &choice);
switch(choice)
{
case 1: add();
break;
case 2: listind();
break;
case 3: listall();
break;
case 4: delet();
break;
case 5: payroll();
break;
case 6: break;
default: printf("Please select a valid option.\n"
;menu();
break;
}
}
while(choice < 6);
}
void add()
{
short x, ct, emptemp;
printf("How many records would you like to add?\n"
;scanf("%d", &x);
//Loop the correct number of times
for(ct = 0; ct<x; ct++)
{
//Set the adding pointer to the beginning (ptr_head) of the tree structure
ptr_temp = ptr_head;
//Get a temporary empnum to determine location of the new record.
printf("Please enter the employee number.\n"
;scanf("%d", &emptemp);
//Find the location of the new record
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//If the temporary empnum is greater than the current, and the
//right link isn't null, move right.
if(emptemp > ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_temp=ptr_temp->right;
}
//If the temporary empnum is lower than the current, and the
//left link isn't null, move left.
if(emptemp<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_temp=ptr_temp->left;
}
}
//If the temporary empnum is lower than the current,
if(emptemp < ptr_temp->empnum)
{
//Create a new record on the left. Point to it.
ptr_temp->left = new SER;
ptr_temp = ptr_temp->left;
}
else
{
//Otherwise it's higher than the current.
//Create a new record on the right. Point to it.
ptr_temp->right = new SER;
ptr_temp = ptr_temp->right;
}
//Finally we point to the new record in it's proper position, so we can store the
//temporary employee number.
ptr_temp->empnum = emptemp;
//Store the rest of the data.
printf("Please enter the employee's name.\n"
;scanf("%s", ptr_temp->name);
printf("Please enter the employee's pay code.\n"
;scanf("%d", &ptr_temp->pc);
printf("Please enter the employee's salary.\n"
;scanf("%f", &ptr_temp->sal);
ptr_temp->left = NULL;
ptr_temp->right = NULL;
}
printf("\n\n\n"
;}
void listind()
{
//This is a the choice variable and a flag.
short choice;
//Get an employee number to determine location of the record to be printed.
printf("Please enter the employee number.\n"
;scanf("%d", &choice);
//Set the temporary pointer to the top of the tree.
ptr_temp = ptr_head;
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//If the employee number is greater than the current, and the
//right link isn't null, move right.
if(choice>ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_temp=ptr_temp->right;
}
//If the employee number is lower than the current, and the
//left link isn't null, move left.
if(choice<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_temp=ptr_temp->left;
}
}
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
printf("\n\n\n"
;}
void listall()
{
/*
//Set the temp pointer to the top of the tree.
ptr_temp = ptr_head;
//Loops and prints
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL)
{
//Print the current record
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
//Advance down the tree
}
printf("\n\n\n"
;*/
}
void delet()
{
short choice, lrflag=3;
char confirm = 'n';
SER *ptr_saved, *ptr_del;
printf("Please enter the employee number of the employee you would like to delete.\n"
;scanf("%d", &choice);
//Set the temporary pointer to the top of the tree.
ptr_temp = ptr_head;
while(ptr_temp->right!=NULL && ptr_temp->left!=NULL && ptr_temp->empnum!=choice)
{
//If the employee number is greater than the current, and the
//right link isn't null, move right.
//lrflag will tell us whether the last move was from a left or right link.
if(choice>ptr_temp->empnum && ptr_temp->right!=\0)
{
ptr_saved=ptr_temp;
ptr_temp=ptr_temp->right;
lrflag=2;
}
//If the employee number is lower than the current, and the
//left link isn't null, move left.
if(choice<ptr_temp->empnum && ptr_temp->left!=\0)
{
ptr_saved=ptr_temp;
ptr_temp=ptr_temp->left;
lrflag=1;
}
}
//For once, we DON'T have to worry about the first record.
printf("%d\t%s\t%d\t$%7.2f\n", ptr_temp->empnum,ptr_temp->name,ptr_temp->pc,ptr_temp->sal);
printf("Are you sure you wish to delete this record? (y/n): "
;getchar();
scanf("%c", &confirm);
//Confirmation
if(confirm == 'y')
{
if(ptr_saved->left!=NULL && ptr_saved->right!=NULL && ptr_temp->left!=NULL && ptr_temp->right!=NULL)
{
if(lrflag == 1)
{
ptr_del = ptr_saved;
ptr_del = ptr_del->right;
while(ptr_del->left!=NULL && ptr_del->right!=NULL)
{
ptr_del = ptr_del->left;
}
ptr_del->left = ptr_temp->left;
ptr_del->right = ptr_temp->right;
}
if(lrflag == 2)
{
ptr_del = ptr_saved;
ptr_del = ptr_del->left;
while(ptr_del->left!=NULL && ptr_del->right!=NULL)
{
ptr_del = ptr_del->right;
}
ptr_del->left = ptr_temp->left;
ptr_del->right = ptr_del->right;
}
}
else
{
if(ptr_temp->left!=NULL && lrflag == 1 || ptr_temp->left!=NULL && ptr_saved->left==NULL)
{
ptr_saved->left = ptr_temp->left;
}
if(ptr_temp->right!=NULL && lrflag == 2 || ptr_temp->right!=NULL && ptr_saved->right==NULL)
{
ptr_saved->right = ptr_temp->right;
}
}
delete ptr_temp;
printf("Record deleted.\n"
;}
printf("\n\n\n"
;}
void payroll()
{
/* double tpay = 0;
short pc1=8*5*52, pc2=5*52;
//Set the temp pointer to the top
ptr_temp = ptr_top;
//loops, calculates a value.
do
{
switch(ptr_temp->pc)
{
case 1: tpay = tpay + ptr_temp->sal*pc1;
break;
case 2: tpay = tpay + ptr_temp->sal*pc2;
break;
case 3: tpay = tpay + ptr_temp->sal*52;
break;
case 4: tpay = tpay + ptr_temp->sal*26;
break;
default: break;
}
//Advance onward!
ptr_temp = ptr_temp->link;
}
//Until we hit the fence.
while(ptr_temp != NULL);
printf("The total payroll is: $%7.2f\n\n\n", tpay);
*/
}
Zyrenthian
Programmer
Off the top of my head, I cant think of an easy way to list the tree through itteration. If you are adding nodes and deleting nodes without recursion, then use the same loops you are using there to print the code. BUT... as this is a highschool program, the introduciton to trees will most likely lead to binary search trees / red black trees. The easiest way to do this IS through recursion. If you care to take this route email me at Zyrenthian@home.com and I will see if I can help you out.
- Status
Similar threads
- Locked
- Question
- Locked
- Question