I have a sorted array of integers and I want to create a AVL tree.
To do so, I insert the middle element of the array to the tree, then the middle of the left part of the array and so on (binary logic).
What's going wrong whith my code below?
Thanks

#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode* SearchTree;
struct TreeNode
{
int Element;
SearchTree Left;
SearchTree Right;
};
SearchTree Insert( int X, SearchTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T = (struct TreeNode*)malloc( sizeof( struct TreeNode ) );
if( T == NULL ){
printf( "Out of space!!!" );exit(1);
}
else
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else
if( X < T->Element )
T->Left = Insert( X, T->Left );
else
if( X > T->Element )
T->Right = Insert( X, T->Right );
/* Else X is in the tree already; we'll do nothing */
return T;
}
void arrayToAVL(SearchTree *T,int A[], int left, int right){
int mid;
if (right<left) return;
mid=(left+right)/2;
(*T)=Insert(A[mid],*T);
return arrayToAVL(T,A,left,mid-1);
return arrayToAVL(T,A,mid+1,right);
}
void InOrderPrintTree(SearchTree T){
if (T==NULL) return;
InOrderPrintTree(T->Left);
printf("%d ",T->Element);
InOrderPrintTree(T->Right);
}
int main(){
SearchTree t=NULL;
int A[]={1,3,5,6,8};
//testing insert function
//t=Insert(10,t);t=Insert(5,t);t=Insert(1,t);t=Insert(12,t);
InOrderPrintTree(t);printf("\n");
arrayToAVL(&t,A,0,4);
InOrderPrintTree(t);
getchar();
return 0;
}

As I said, I have a sorted array and I want to built an AVL tree using the insert function for simple (unbalanced) BS trees. To do so, I insert the middle elemnt of the array, then the middle of the left subarray, and so on (binary logic).
In the specific code snippet, I declare an array A[]={1,3,5,6,8}, I run the avl function, and the bst created has only 1 and 5. I miss all the others.
I cannot find where is the problem in arrayToAVL funcion.
thanks

Note that you didn't say that ;) But thanks for clarifying.

>> I have a sorted array and I want to built an AVL tree using the insert function for simple (unbalanced) BS trees. To do so, I insert the middle elemnt of the array, then the middle of the left subarray, and so on (binary logic).

An AVL tree is self-balancing, and is sorted. So there's no need to have a sorted array for insertion.
You're using the wrong insertion approach. Insertion into an AVL tree happens "at the root" - the tree insertion algorithm itself takes care of where to place the value, and whether or not to re-arrange (re-balance) the tree.

For insertion, first you find the location where the new node has to be inserted, and then, depending on a few possible situations, you insert the node there by re-arranging the nodes around it.

>> In the specific code snippet, I declare an array A[]={1,3,5,6,8}, I run the avl function, and the bst created has only 1 and 5. I miss all the others.

So, instead of trying to make this approach work, I recommend writing an actual AVL tree insertion implementation.

Either way, the problem in your current code is that you have two return statements in the arrayToAVL function :

The idea is to have only one return statement in the arrayToAVL function, because now you have one too many.

Note also that the arrayToAVL function does not return anything ... so you don't even need a return statement (in fact it's wrong to return something).

So, just remove the return's, and just call the function recursively twice.

What result are you getting now ? Please be more precise when you refer to a problem. The more information you can give, the easier it is for us to help you, and the faster you'll get your answer.

my friend, I dont refer to teh specific results, because I believe that you will run the code with copy-paste. It is time consuming to explain the results of a code snippet...If you can help...

I don't have a compiler available atm. Nor do I have a lot of time.

You know the problem you're referring to ... It can't be that hard to just tell me. Otherwise you'll have to wait until I have the time to analyse your code in detail.

Btw :

>> It is time consuming to explain the results of a code snippet...

Why don't you just copy-paste the output ? That can't be that time consuming, can it ?

ok! the output is 1,3,4,5 ,and it is the 1st half of the array. That happens because the function returns always at line 43, so the second half of the array is never accessed.

Sorry
But I have posted the solution before is not the same as yours.....
Your code having.......
void arrayToAVL(SearchTree *T,int A[], int left, int right){
int mid;
if (right<left) return;

I have put
arrayToAVL(T,A,left,mid-1);
arrayToAVL(T,A,mid+1,right);
instead of
return arrayToAVL(T,A,left,mid-1);
return arrayToAVL(T,A,mid+1,right);
because return was creating the problem....
try to run the code with these corrections...
Its working fine here....

By clicking you are agreeing to Experts Exchange's Terms of Use.

Featured Post

Poor audio quality is one of the top reasons people donâ€™t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Preface
I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net. To view more iPhone tutorials, visit www.sdkexpert.net.
This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦