• 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;  
        }

Open in new window

xiromdimAsked:
Who is Participating?
 
phoffricConnect With a Mentor 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
 
mnhCommented:
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
 
phoffricCommented:
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
Improved Protection from Phishing Attacks

WatchGuard DNSWatch reduces malware infections by detecting and blocking malicious DNS requests, improving your ability to protect employees from phishing attacks. Learn more about our newest service included in Total Security Suite today!

 
phoffricCommented:
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
 
xiromdimAuthor Commented:
I will try to change the function to void... I 'll come back soon.
0
 
phoffricCommented:
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
 
xiromdimAuthor Commented:
very good advice, but he didn't give some code
0
 
phoffricCommented:
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.

All Courses

From novice to tech pro — start learning today.