[SOLVED] novice : help with recurrent code

atlantis43 · 06-14-2015, 08:40 PM

Sorry for having posted this severely flawed code & wasted time of so many of you who viewed it.

Code:

    int rte = 0; //binary value of left/right pointer
    short rootpath[16];

/*Given a binary tree, print out all of its root-to-leaf binary
paths, one per line. Uses a recursive helper to do the work.*/
void printPathArray(short rootpath[], int len)
{
    int i;
        //to include tree for single character input
    if (len == 1)
        printf("0");

    else
    {
            // to eliminate extra preceding '0' in array
        for(i=1; i < len; i++)
        {
            printf("d ",rootpath[i]);
        }
    }
    printf("\n");
}

/*void printPathsRecur()
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf binary paths.*/
void printPathsRecur(struct node* node, int pathLen, int rte)
{
    if (node == NULL)
        return;
    // append this node to the path array
    rootpath[pathLen] = rte;
    pathLen++;

        // if it's a leaf, print the path that led to here ( 0's and 1's')
        // and then print the symbol for the path
    if (node->left == NULL && node->right == NULL) 
    {   // pathLen is used for array index for print
        printPathArray(rootpath, pathLen);
        // print alphabetic symbol corresponding to the above path            
        printf("c\n",node->symbol);
    }
    else
    {
        // otherwise try both subtrees
        printPathsRecur(node->left, pathLen, 0); 
        printPathsRecur(node->right, pathLen, 1);
    }
}

ButterflyMelissa · 06-15-2015, 05:18 PM

Quote:

Sorry for having posted this severely flawed code & wasted time of so many of you who viewed it.

Dont ever apologise for asking a question, no matter how silly YOU think the question is...never apologise. Humans have one (if any) good quality: asking questions...
So, the code had a few flaws....that's okay.
Can I invite you to share the solution on a bit more expanded scale? That way, the rest can benefit too

Thanks
Thor

atlantis43 · 06-16-2015, 09:54 AM

Okay, so I'll re-post question a bit more clearly, as it was not really solved.
Im vaguely aware that code lines can be executed either before or after the recurrent call, but Im not sure if this feature is applicable to the type of recurrent code Im using.
In working on a problem to solve Huffman coding, I've developed the following sample code to view a table for values to make the bit stream, which prints the path from root to leaf. Forgive what I'm sure is the amateurishness of my code, but I'm hoping that someone could tell me how this code can be changed so as to reverse the output of the recurrent function, ie, print the path from leaf to root. I hope that I've included enough comments to make my code readable. Please advise!
(I realize that I could just reverse the output as array elements, but I'd prefer to understand how to properly achieve my goal).

Code:

//printbits.c
    int rte = 0; //binary value of left/right pointer
    short rootpath[16];

/*Given a binary tree, print out all of its root-to-leaf binary
paths, one per line. Uses a recursive helper to do the work.*/
void printPathArray(short rootpath[], int len)
{
    int i;
        //to include tree for single character input
    if (len == 1)
        printf("0");

    else
    {
            // to eliminate extra preceding '0' in array
        for(i=1; i < len; i++)
        {
            printf("d ",rootpath[i]);
        }
    }
    printf("\n");
}

/*void printPathsRecur()
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf binary paths.*/
void printPathsRecur(struct node* node, int pathLen, int rte)
{
    if (node == NULL)
        return;
    // append this node to the path array
    rootpath[pathLen] = rte;
    pathLen++;

        // if it's a leaf, print the path that led to here ( 0's and 1's')
        // and then print the symbol for the path
    if (node->left == NULL && node->right == NULL) 
    {   // pathLen is used for array index for print
        printPathArray(rootpath, pathLen);
        // print alphabetic symbol corresponding to the above path            
        printf("c\n",node->symbol);
    }
    else
    {
        // otherwise try both subtrees
        printPathsRecur(node->left, pathLen, 0); 
        printPathsRecur(node->right, pathLen, 1);
    }
}

ButterflyMelissa · 06-17-2015, 02:52 AM

Quote:

Forgive what I'm sure is the amateurishness of my code

No need to, code has to perform, not win a beauty contest

Is this about data compression? Would the term DEcompression be valid?
I looked at the (hopfully) relevant Wikipedia page....lotsa math...hmm...
Thor

ntubski · 06-17-2015, 04:40 AM

Quote:

Originally Posted by atlantis43

Okay, so I'll re-post question a bit more clearly, as it was not really solved.
Im vaguely aware that code lines can be executed either before or after the recurrent call, but Im not sure if this feature is applicable to the type of recurrent code Im using.

That doesn't help for printing all the paths backwards. To see why, try tracing the path that the recursive calls will take through the tree. It would be applicable if you were trying to print a single path backwards.

As to the code, it's a bit confusing to have the unused global rte with the same name as a local. Also, the name "rte" seems a bit obscure to me. And I wouldn't drop the braces from the if (len == 1) because its corresponding else does have braces.

Did you miss pathLen+1 in the recursive call?

Finally, I don't think the special case for height 1 tree should be needed, but I guess removing it would require changing the caller of printPathsRecur(), which you haven't posted.

Quote:

Originally Posted by Thor_2.0

No need to, code has to perform, not win a beauty contest

Not beauty necessarily, but readability is important.

Quote:

Originally Posted by sicp

a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute.

https://mitpress.mit.edu/sicp/front/node3.html

ButterflyMelissa · 06-17-2015, 04:41 AM

Quote:

Not beauty necessarily, but readability is important.

hmm...touche

atlantis43 · 06-17-2015, 07:46 AM

Quote:

Originally Posted by Thor_2.0

Is this about data compression? Would the term DEcompression be valid?

Yes, I'm thinking such a modification of the 'same' code would be useful for DEcompression

Quote:

I looked at the (hopfully) relevant Wikipedia page....lotsa math...hmm...
Thor

Yup: been there, done that.

atlantis43 · 06-17-2015, 08:30 AM

Quote:

Originally Posted by ntubski

That doesn't help for printing all the paths backwards. To see why, try tracing the path that the recursive calls will take through the tree. It would be applicable if you were trying to print a single path backwards.

Okay, I'll have to go thru the suggested tracing, but that's the simple answer I was seeking!

Quote:

As to the code, it's a bit confusing to have the unused global rte with the same name as a local. Also, the name "rte" seems a bit obscure to me. And I wouldn't drop the braces from the if (len == 1) because its corresponding else does have braces.

For me, 'rte' was a quick abbreviation to mean 'route' (as opposed to 'root'). Guess I should have just used 'path'. Also, your style comment is noted.

Quote:

Did you miss pathLen+1 in the recursive call?

Do you mean for a terminating character? If so, I'm aware that I'll need that, but this code is just preliminary-----haven't yet included it. If you mean something else (besides the already present code line---)

Code:

    pathLen++;

-----please advise.

Quote:

Finally, I don't think the special case for height 1 tree should be needed, but I guess removing it would require changing the caller of printPathsRecur(), which you haven't posted.

Caller is:

Code:

    printPathsRecur(root, 0, rte);

Code written to include compression for even a single character, which (I think) required passing a '0' with the caller, so this seemed necessary: otherwise I got an extra preceding '0' for all character bitcodes.
Thanks with all the help with me trying to re-invent the wheel :-)

ntubski · 06-17-2015, 03:20 PM

Quote:

Originally Posted by atlantis43

For me, 'rte' was a quick abbreviation to mean 'route' (as opposed to 'root'). Guess I should have just used 'path'.

I think 'path' is more standard graph theory terminology, but using 'route' would be fine too. It's just not worth using a non-standard abbreviation to save all of 2 characters. Except that, this variable is not the route, it's just a single step. So it's misnamed.

Quote:

Did you miss pathLen+1 in the recursive call?

Do you mean for a terminating character? If so, I'm aware that I'll need that, but this code is just preliminary-----haven't yet included it. If you mean something else (besides the already present code line---)

Code:

    pathLen++;

-----please advise.

I meant

Code:

    else
    {
        // otherwise try both subtrees
        printPathsRecur(node->left, pathLen+1, 0); 
        printPathsRecur(node->right, pathLen+1, 1);
    }

Quote:

Caller is:

Code:

    printPathsRecur(root, 0, rte);

Code written to include compression for even a single character, which (I think) required passing a '0' with the caller, so this seemed necessary: otherwise I got an extra preceding '0' for all character bitcodes.

What's the value of rte in the caller? You should rethink your interface (there is no correct value of rte that the caller can give: you don't go left or right to reach the root).

atlantis43 · 06-19-2015, 12:13 PM

Quote:

Originally Posted by ntubski

I think 'path' is more standard graph theory terminology, but using 'route' would be fine too. It's just not worth using a non-standard abbreviation to save all of 2 characters. Except that, this variable is not the route, it's just a single step. So it's misnamed.

Yes, changed some var names as per your suggestion.

[QUOTEI meant

Code:

    else
    {
        // otherwise try both subtrees
        printPathsRecur(node->left, pathLen+1, 0); 
        printPathsRecur(node->right, pathLen+1, 1);
    }

Quote:

What's the value of rte in the caller? You should rethink your interface (there is no correct value of rte that the caller can give: you don't go left or right to reach the root).

As I've learned to take the time to evaluate exactly what you're saying, I now realize that, though my code was giving correct output, the incrementation should occur in the recurrent call:

Thanks again.

ntubski · 06-20-2015, 04:04 AM

Quote:

Originally Posted by atlantis43

As I've learned to take the time to evaluate exactly what you're saying, I now realize that, though my code was giving correct output, the incrementation should occur in the recurrent call:

Oh, sorry I didn't actually clue in to the pathLen++ part, even though you pointed it out. I just expected the increment to be on recursive call, so it didn't really occur to me to look elsewhere for it. Just a style issue then (though obviously my style is objectively better

).