Helo with building binary trees using pointers
Hi to everyone. I'm currently working on a school homework using binary trees. I feel as though I'm almost finished, but I have a problem I couldn't figure out to solve.
Although I have a general idea of how structures and pointers work, I still get confused with their usage. I've been searching the internet for a comprehensive explanation of how they work but most of what I've found lack the details that I need to know. So I came here hoping someone can explain these things better. Forgive me 'coz I really have a poor comprehension when it comes to pointers.
My algorithm constructs a binary tree given the preorder and inorder sequence (in the form of strings).
So I have a global structure declared this way:
Code:
struct Node{
char letter;
struct Node *left;
struct Node *right;
};
and a global pointer to the root.
this is the rest of the code:
Code:
int main(){
char preorder[5]="RASIN"; preorder[5]='\0';
char inorder[5]="SAIRN"; inorder[5]='\0';
root=malloc(sizeof(struct Node));
*root=buildTree(preorder, inorder); //this line starts the construction of the tree from the root to its branches
getch();
}
struct Node buildTree(char *preorder, char *inorder){ //I'm using a recursive method to build the tree. This is how I visualize the algorithm:
struct Node *newNode=malloc(sizeof(struct Node));
if(strlen(inorder)==1){
newNode->left=NULL;
newNode->right=NULL;
newNode->letter=inorder[0];
return *newNode;
}
int index = findLetterToPut(preorder, inorder);
*newNode->left = buildTree(preorder, substr(inorder, 0, index));
*newNode->right = buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
newNode->letter = inorder[index];
return *newNode;
}
this is the function findLetterToPut(...):
Code:
int findLetterToPut(char *preorder, char *inorder){
int index1, index2;
for(index1=0; index1<strlen(preorder); index1++){
for(index2=0; index2<strlen(inorder); index2++){
if(preorder[index1]==inorder[index2] )
return index2;
}
}
}
The program works properly if I remove this line from the buildTree function:
Code:
*newNode->right = buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
However, only the left nodes are constructed without that line. The good thing is that these nodes are constructed properly. All pointers to the right node (starting from the root)are therefore NULL without this line.
My question is: what's the problem with that line? If I include that line, an execution error occurs, e.g., illegal operation. That line is essential for constructing the right nodes.
Thanks for your time. :)