how to make a non-recursive function from recursive

[janbily1]

Hi, could you help me with my problem? How to make a non-recusrsive function from a recursive one? This is my recursive function (function locates the node with a specified key in binary search tree)

/* Key x - searched key in the tree                                    */
/* Bvs t - pointer to the root of the tree                             */
/* return value - pointer to found node, NULL if the key was not found */
Position Member ( Key x, Bvs t )
        {
                 Position pos = NULL;
                 
                 if (t == NULL) return NULL;
                 if (t -> key == x) return (Position)t;
                 if (t -> key < x) pos = Member(x, t -> right);
                 if (t -> key > x) pos = Member(x, t -> left);
                 
                 return pos;
        }

Could you write me a non-recursive? Thanks...

[Bazzy]

You can make a loop on t where the recursive calls become modifications of t itself

[janbily1]

So the first 2 if conditions are OK and I only have to change conditions where function Member is called? And do I not have to use labels? Sorry if my questions are stupid, but I am noob in programming...

[Bazzy]

You need to wrap all the four in a loop. You can use an infinite loop and the returns to break it.
You need to change the bodies of the last two ifs ( of course since is there that your function is recursive )

[janbily1]

I tried many things to do, but I simply just dont get it...

                 Position pos = NULL;
                 if (t == NULL) return NULL;
                 
                 while (t -> key == x) 
                 {
                       if (t -> key < x) t -> key = t -> right; 
                       if (t -> key > x) t -> key = t -> left; 
                 }
                 return pos;

Is this close to solution or is it absolutely wrong? Where/when should I assign t to pos? thanks

[Bazzy]

You don't really need pos.

if (t == NULL) return NULL;
if (t -> key == x) return (Position)t;

Should be in the loop and the loop condition is wrong

[janbily1]

Ok, so, programm seems to work correctly, but only for sure. Is this right?

while (t -> key = x) 
                 {
                       if (t == NULL) return NULL;
                       if (t -> key == x) return (Position)t;
                       if (t -> key < x) t -> key = t -> right;
                       if (t -> key > x) t -> key = t -> left;
                 }

[Computergeek01]

No. no it's not. What Bazzy meant by "the loop condition is wrong" isn't that it was coded wrong but that the condition of the loop excludes either of the two if statements within the loop from being met. Just assigning 'key' to 'x' still isn't working.

[janbily1]

Then I really have no idea what should be the condition. For me, condition is met when I find x. And I thought, that when pointer t is assigned or is equel to x it should work...

[jimc]

I think you need to read up on how binary tree is organized before attempting this, and before asking some one else to write it for you. The code you have above should not even compile since you are trying to assign to an incompatible type, among several other issues.