Listing all nodes in a 'Tree'

Chemakill · Apr 17, 2001

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.

Karl Blessing · Apr 18, 2001

it is true that anything you can do with rescursion you can do without, the only problem is , the reason rescursion is the popular method, is because doing it without it on things like binary trees, and dynamic(to the user) length linked lists, is that its a pretty bad brain cruncher(least in my opinion) to write.

I could help you out with the rescrusive method instead if you like. Karl Blessing aka kb244{fastHACK}

Guest_imported · Apr 18, 2001

My login isn't working right. So I have to pretend to be myself. And that's only the second weirdest thing to happen today. Anyhow, I solved the delete problem. And I really need to do this list all without recursion. Somehow.

The following is my code. There is a problem though. Copy paste and compile, and tell me if you get "Illegal escape sequence" errors. You should get six.

//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&quot

;
}

void menu()
{
short choice;
//The menu loop
do
{
printf("Menu\n\n&quot

;
printf("1. Add a record.\n2. List a record.\n3. List all records\n&quot

;
printf("4. Delete a record.\n5. Calculate total payroll.\n6. Exit\n&quot

;
printf("\nYour choice: &quot

;
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&quot

;
menu();
break;
}
}
while(choice < 6);
}

void add()
{
short x, ct, emptemp;

printf("How many records would you like to add?\n&quot

;
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&quot

;
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&quot

;
scanf("%s", ptr_temp->name);

printf("Please enter the employee's pay code.\n&quot

;
scanf("%d", &ptr_temp->pc);

printf("Please enter the employee's salary.\n&quot

;
scanf("%f", &ptr_temp->sal);

ptr_temp->left = NULL;
ptr_temp->right = NULL;
}
printf("\n\n\n&quot

;
}

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&quot

;
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&quot

;
}

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&quot

;
*/
}

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&quot

;
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): &quot

;
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&quot

;
}

printf("\n\n\n&quot

;
}

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);
*/
}

//Yes this is high school programming class. But we were told to figure it out however we could, Internet and tech forums included, so don't let guild prevent you from helping. Thx.

Guest_imported · Apr 18, 2001