Originally Posted by
kellyjosephpric
Alright, I removed the if statement, as it was unnecessary.
What if statement? As a small side note, before I get into the big stuff, you correctly declared main to return an int, so please put a return 0 at the bottom of main. Also, you should have seen this as a warning from the compiler, if not (or even if you did and ignored it), please turn on all your warnings when you compile and make sure they're resolved.
I defy you to tell me it doesn't solve the problem.
Haha! I defy you! It doesn't solve the problem (at least not entirely). I actually agree that your general approach works, but there is some small bug causing your list to not always be circular. Perhaps it's the mysterious if statement you speak of, but I can only test the code you've posted, not whatever you changed. If you insert pre-ordered data into a binary tree you effectively have a linked list. If this data is ascending, you have every node going all the way down the right/large branch to be inserted at the bottom. If the data is descending, it goes all the way down the left/small side. Maybe this has something to do with it.
I tried an ascending, a descending, and a couple of different sets of ints. The only problem that I can find now, is that it's difficult to tell what's happening by reading the code.
I made the following change to your code in sample.c (post #5) to cause the crash:
Code:
int data[10] = {6, 3, 7, 0, 4, 9, 2, 5, 1, 8},
becomes
Code:
int data[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
I can follow the gist of your code just fine
Thing is, I don't know where that bug was. It seems like it was in printList().
working:
Code:
void printList(NODE *node)
{
NODE *head = node;
do
{
printf("%d ", node->data);
node = node->large;
}
while(node != head);
return;
}
not working:
Code:
void printList(NODE *list)
{
NODE *node = list;
do
{
printf("%d ", node->data);
node = node->large;
}
while(node != list);
return;
}
What?! Am I totally confused?
Probably. Those two pieces of code are identical, except for the names of the parameter and the local variable. Your implementation of printList does the job assuming you have a perfectly constructed list, but if something is awry, as it seems to be for the input data I mentioned above (your list isn't circular in that case), your program seg faults. I modified printList to look like this to show you the null pointers at the start and end of your list:
Code:
void printList(NODE *list)
{
NODE *node = list;
while (node) {
printf("data: %d small: %p large: %p\n", node->data, node->small, node->large);
node = node->large;
}
return;
}
Anyway, so would you say that what I wrote is an in-order traversal? It descends to the smallest and then links each next larger as the next and last in the list.
Yes. You process the current/root node IN between processing the left and right subtrees.
What then does a pre-order or post-order traversal look like?
Preorder:
process root // PRE processing of the subtrees
process left subtree
process right subtree
Preorder:
process left subtree
process right subtree
process root // POST processing of the subtrees