First of all, this is a homework related problem.
I'm trying to solve the Stanford Binary Tree to Doubly Linked List problem.
Tree List Recursion Problem
I'm kind of stumped...I don't get why it falls into a loop. It builds a tree that looks like this:
6
/ \
3 7
/ \ \
0 4 9
\ \ /
2 5 8
/
1
It makes it as far as setting the head to '0', descending to '1', then it loops between 0 and 1!
I don't understand why it doesn't return to '2'. If you could be so kind as to help me understand why. Is it a pointer problem? Do I not understand the recursive algorithm? Static variables?!
Just a nudge in the right direction, please.
Code:
10 struct node
11 {
12 int data;
13 struct node *small;
14 struct node *large;
15 };
16
17 typedef struct node NODE;
18
19
20 int main(void)
21 {
22 NODE *genTree(int *data);
23 NODE *treeToList(NODE **current);
24 void printTree(NODE *tree);
25 void printList(NODE *list);
26
27 NODE *tree, *list;
28 int data[10] = {6, 3, 7, 0, 4, 9, 2, 5, 1, 8},
29 i = 0;
30
31 printf("Data:\n");
32 for( ;i < 10; i++)
33 printf("%d ", data[i]);
34 printf("\n");
35
36 tree = genTree(data);
37 printf("Data in tree:\n");
38 printTree(tree);
39 printf("\n");
40
41 list = treeToList(&tree);
42 printf("Data in list:\n");
43 printList(list);
44 printf("\n");
45 }
46
47 NODE *treeToList(NODE **current)
48 {
49 void link(NODE *smaller, NODE *larger);
50
51 static NODE *tail = NULL,
52 *head = NULL;
53
54 if(!(*current)) return NULL;
55
56 treeToList(&(*current)->small);
57
58 if(!head)
59 head = *current;
60
61 if(tail != NULL)
62 link(tail, *current);
63
64 tail = *current;
65
66 treeToList(&(*current)->large);
67
68 link(tail, head);
69
70 return head;
71 }
72
73 void link(NODE *small, NODE *large)
74 {
75 small->large = large;
76 large->small = small;
77 }