binary search tree print function: Logic not clear-help

[csstudent123]

Hello. Pls explain to me

1) how come root node is printed when the first call to function goes to left subtree?

2) How it resets to root to go to right subtree from last left tree leaf?

void bst:: printNodes(hwareItem*& root){

    if(root){
        printNodes(root->left);
        cout<<root->barcode<<endl;
        cout<<root->description<<endl;
        cout<<root->price_per_unit<<endl;
        cout<<root->stock<<endl;
        printNodes(root->right);}

}

[Aceix]

I don't get you. This uses recursion(calling a function from itself)

Aceix.

[dhayden]

The code looks fine to me. If the results aren't what you expect then maybe the structure of the tree isn't what you think?

2) How it resets to root to go to right subtree from last left tree leaf?

The beauty of recursion is that each call has different parameters (and local variables). So you don't need to "reset to root": when you return from a lower call, the previous value of root is there unchanged. Actually, to express this better in your code, don't make root a reference, and call it subtree:

void bst:: printNodes(hwareItem* subtree){

    if(subtree){
        printNodes(subtree->left);

        cout<< subtree->barcode << '\n';
        cout<< subtree->description << '\n';
        cout<< subtree->price_per_unit<< '\n';
        cout<< subtree->stock <<endl;

        printNodes(subtree->right);
   }

}

I've also replaced all but the last endl with '\n'. This will speed up the output y not flushing so frequently.

[csstudent123]

thanks...So it is ok to say variables are not replaced for each call? But is stored in stack all the updates?

[dhayden]

That's right. When you call a function, the program allocates space on the stack for the parameters and local variables. This happens even when you make a recursive call: so each call has it's own set of local variables and parameters. In practice the compiler can sometimes optimize some of this away - such as by storing parameters in CPU registers instead of the stack, but think of that as an optimization - conceptually it's new space for each call.

[csstudent123]

Thanks...I will get back if I need help... :)

[csstudent123]

Why is that if I want to delete a node in single linked list I have to do it from head? I had two nodes in a list. I could delete head but to delete tail I had to copy tail to head and head to tail and then delete head so remove tail data from before...Why is that?

[kbw]

Why is that if I want to delete a node in single linked list I have to do it from head?

You don't have to, you can delete from anywhere in the list, but you have to make sure that the link that pointed to the item you delete, points to the next one on in the chain.

I had two nodes in a list. I could delete head but to delete tail I had to copy tail to head and head to tail and then delete head so remove tail data from before...Why is that?

That's all very confusing, you're looking at it the wrong way.

Draw out the linked list on paper, and it'll be obvious what needs to be done.
http://computer.howstuffworks.com/c32.htm

[csstudent123]

How could I write the removeNode code shorter?

int linkedlist:: remNode(trans*& head, char inv[]){

    trans *prev, *curr, *tmp;

    if (head==NULL){
        cout<<"Nothing to remove in the list"<<endl;
        return -1;
    }
    else{
        curr=head;
        prev=head;
        while(curr!=NULL){

            if(curr==head){

                if(strcmp(inv, curr->inv_num)==0){

                    head=curr->next;
                    strcpy(head->hware_item_bar, curr->next->hware_item_bar);
                    strcpy(head->inv_num, curr->next->inv_num);
                    head->qt_pchase=curr->next->qt_pchase;
                    head->total_price=curr->next->total_price;
                    delete curr;

                    return 0;
                    }
                else
                    return -1;
                }
            else if (head->next->next==NULL){


                if(strcmp(inv,head->next->inv_num)==0){


                    curr=head->next;
                    strcpy(curr->hware_item_bar, head->hware_item_bar);
                    strcpy(curr->inv_num, head->inv_num);
                    curr->qt_pchase=head->qt_pchase;
                    curr->total_price=head->total_price;

                    delete head;
                    head=curr;;

                    strcpy(head->hware_item_bar, curr->hware_item_bar);
                    strcpy(head->inv_num, curr->inv_num);
                    head->qt_pchase=curr->qt_pchase;
                    head->total_price=curr->total_price;

                    return 0;

                        }
                else
                    return -1;

            }

            else if(curr){
                if(strcmp(inv,curr->inv_num)==0){

                    prev->next=curr->next;

                    strcpy(prev->next->hware_item_bar, curr->next->hware_item_bar);
                    strcpy(prev->next->inv_num, curr->next->inv_num);
                    prev->next->qt_pchase=curr->next->qt_pchase;
                    prev->next->total_price=curr->next->total_price;

                    delete curr;

                    return 0;


                }

                else
                    return -1;

            }

                prev=curr;
                curr=curr->next;

        }

    }

}

[kbw]

You shouldn't be copying things, once you've found the node, delete it.

1. Move the string compare as the top level test inside the loop, as that's what you really care about.
2. You're deleting a node, so I don't know why you're copying things--I removed all that code
3. Make the function return the number of entries deleted.
4. Remove redundant if then/else clauses.
5. Move variable declarations to where they're used.
6. curr becomes invalid after it's deleted, so reset it after deletion.
7. Add const to the string parameter

int linkedlist::remNode(trans*& head, const char inv[]) {
	int count = 0;

	trans *curr = head;
	trans *prev = head;
	while (curr != NULL) {
		if (strcmp(inv, curr->inv_num) == 0) {
			if (curr == head) {
				trans* tmp = head;

				head = head->next;
				prev = head;

				delete tmp;
			}
			else {
				trans* tmp = curr;

				prev->next = curr->next;

				delete tmp;
			}

			curr = prev->next
			++count;
		}
		else {
			curr = curr->next;
		}
	}

	return count;
}

[csstudent123]

Thanks :). I have one more question

Please tell me what am I doing wrong. I wish to add a node in a certain position..say it is before position where value is 0.

int patients:: addPatientEmg(patient*& head, ptient ptn){

    patient *curr, *prev, *tmp;


    if(head==NULL){
        addPatient(head,ptn);
        return 0;}
    else{

        curr=head;


        while(curr->next!=NULL){
            prev=curr;

            if(curr->next->priority==0){
                tmp=new patient;
                strcpy(tmp->name, ptn.name);
                tmp->priority=ptn.prio;

                prev->next=tmp;
                tmp->next=curr->next;

                break;


            }


            curr->next=curr->next->next;
        }


    }
    return 0;

}

[kbw]

You first have to find the value that has zero:

	trans *curr = head;
	while (curr != NULL) {
		if (curr->priority == 0) {
			// do the insert here
			break;
		}

		curr = curr->next;
	}

Then you do the insert:

			// create a new node
			trans* p = new trans;
			p->priority = ptn.prio;
			strncpy(p->name, ptn.name, sizeof(p->name) - 1);

			// insert it into the linked list
			p->next = curr->next;
			curr->next = p;

[csstudent123]

I did like this above, but I know I am wrong, but whats the logic error, I cant seem to visualise...

[kbw]

I posted a link earlier that has good diagrams and accompanied by a good explanation. Did you look at it?

[csstudent123]

Would it be possible to give something in C++ picture format?

[kbw]

You obviously didn't read the link; maybe someone else can help.

[csstudent123]

I did..Its in C but any way I will try to learn the C malloc syntax...thanks though

[kbw]

The data structures are same in C as it is in C++.

The point is memory is take of a heap and used in some structure. That link explains the who thing; from the rationale of using pointers to useful data strucutres.

[dhayden]

Here is another site that has pictures of a linked list:
http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists.html

The algorithm to insert into a sorted list is:
if the list is empty or the new item goes before the first item then
insert new item at the head.
else
walk prev and curr pointers down the list until curr points AFTER where new item goes
insert new item between prev and curr

[csstudent123]

thanks :)