Jeff Greene - 9 months ago 41

C Question

I am trying to build a specific type of tree, where each internal node's data relies on the leaves of the tree. I have a pre-order array,

`pre[] = { 0,0,0,1,2,3,0,4,5}`

`0`

/ \

0 0

/ \ / \

0 3 4 5

/ \

1 2

I am having trouble with the recursive call, specifically in the while loop. After I finish with creating the node with data "2", after I return the root I am left at the internal node right above it. This internal node will continue to run in the while loop and mess up my tree. If I decide to place a return root within the while loop at the end of the condition statements then the construction will stop after filling up the left side of the tree. How can I fix this?

`1 #include <stdio.h>`

2 #include <stdlib.h>

3 #include <limits.h>

4

5 struct node

6 {

7 int data;

8 int leafNode;

9 struct node *left;

10 struct node *right;

11 };

12

14 struct node* newNode (int data){

15 struct node* temp = (struct node *) malloc(sizeof(struct node));

16 temp->data =data;

17 temp->left = temp->right= NULL;

18 return temp;

19 }

22 struct node* _constructTree( int pre[], int * preIndex, int low, int high, int size, int leaf){

23 if (*preIndex >= size || low > high){

24 return NULL;}

25

26 printf("We are about to create this node: %d\n", pre[*preIndex]);

27

28 struct node* root = newNode(pre[*preIndex]);

29 *preIndex = *preIndex + 1;

30 if(leaf){

31 printf("Returning this leaf node: %d\n", pre[*preIndex - 1]);

32 return root;}

33

34

35 if(low == high){

36 return root;}

37

38 while(low<high){

39 if(pre[*preIndex] == 0){

40 root->left = _constructTree(pre, preIndex, *preIndex, high, size, 0);}

41

42 if(root->left == NULL){

43 root->left = _constructTree(pre, preIndex, *preIndex, high, size, 1);

44 return root;

45 }

46 if(pre[*preIndex] != 0){

47 root->right = _constructTree(pre, preIndex, *preIndex, high, size, 1);

48 return root;

49 }

50 else{

51 root->right = _constructTree(pre,preIndex, *preIndex, high, size, 0);}

52 }

53 return root;

54 }

55 }

56

57 struct node * constructTree(int pre[], int size){

58 int preIndex = 0;

59 return _constructTree(pre, &preIndex, 0, size -1, size, 0);

60 }

61

Answer Source

Would something like this not work (slightly summarized but hopefully it shows the idea)?:

```
construct_tree(int pre[], int* index){
root=pre[*index];
*index++;
if(root>0)return root;
left=construct_tree(pre,index);
right=construct_tree(pre,index);
return root;
}
```