• C

# from a sorted array to AVL tree

I want to built a AVL tree from a sorted array (of ints).
Below is my code, but I'm doing something wrong...
``````typedef struct TreeNode* SearchTree;

struct TreeNode
{
int Element;
SearchTree  Left;
SearchTree  Right;
};
SearchTree avl(int A[],int N, int left, int right,SearchTree T){
SearchTree temp=NULL;
int mid = (left+right)/2;printf("mid=%d",mid);getchar();
temp= Insert(A[mid],T);
right=mid-1;printf(" right=%d",right);
if (right<left) return temp;
avl(A,N,left,right,T);
left=mid+1;
if (left>=right) return temp;
avl(A,N,left,right,T);
}
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 )
FatalError( "Out of space!!!" );
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;
}
``````
###### Who is Participating?

Commented:
When inserting the middle element, I believe you are inadvertently missing other elements. You can confirm this in your debugger stepping through each line (or use lots of printf statements).
0

Commented:
Hi,

In function avl(int A[],int N, int left, int right,SearchTree T), why don't you just iterate over the elements of A, inserting them one after the other in the tree?

I don't understand why you keep splitting the array in two and inserting the middle element. This looks incorrect...

Regards,
-- mnh
0

Commented:
Quick look & question for you. Last line in avl() is a recursive call to avl(). But after this last line, you do not return anything. Shouldn't you return a SearchTree?
0

Commented:
Follow-up comment: avl() defined to return SearchTree, and it does do this sometimes; but whenever avl() is called, the return value is ignored. If you do not need a return value, then do not return anything (make return void); if you do need a return value, then use the return value.
0

Author Commented:
I will try to change the function to void... I 'll come back soon.
0

Commented:
I submitted recommendations to the author, which was incorporated into the code submitted in the follow-up question. http://www.experts-exchange.com/Programming/Languages/C/Q_25001363.html?cid=1576

My 3rd comment was the result of debugging the author's code and identifying major tree insertion issue.

So, why close this, and why not award points to contributors?
0

Author Commented:
very good advice, but he didn't give some code
0

Commented:
Hi xiromdim,
I was just starting the dialog with you, and it ended in an hour. I would have answered further questions.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.