Thread: Find al posible routes in a binairy tree

Hi folks,

I'm working on a program witch translates a kind of "assambly" into a code witch my hardware understands. The assably describes a filter(Berkeley Packet Filter). So we work to a true or false. you can write this down as a binairy tree:

Code:

                                 0
                            /           \
                           3            10 
                      /      \         /      \
                     4       6       13      11
                   /  \                       /  \
                 5    6                     12    13

I already parsed out all the paths to false, so in this tree we find all solutions to True. Now, I need to find all this paths and store it somewhere, so i can translate them for the hardware. How can I do that?

My algorithm doesn't find them all...

the variable workstring[50[4] have the following information:
workstring[rulenumber][command]. example:

workstring[1][0]=21; Means a check (the actual assambly command)
workstring[1][1]=0; The jump-troug (always on this place
workstring[1][2]=6; the jump-false, always on this place
workstring[1][3]=34525; The check variable

The jumps are relative.

Code:

int splitsing[20];
///After the parsing, it's time to search for all the paths to (the) true
    for(j=0; j<true_eind; j++)
        {
         if (workstring[j][0]==21)                                      ///detect the split-up
            {
             if (!(workstring[j][2] == 50 || workstring[j][3] == 50))   ///when we parsed a jump
                    {
                     splitsing[routeteller]=j;                          ///sla regel van de spliting op
                     routeteller++;                                     ///controlevariabele, hoog hem een op
                     i++;
                    }
            }
        }
       splitsing[routeteller+1]=0;                                      ///There must be a empty splitter for the first route
    printf("\nwe have %d routes in this program",routeteller); 
/////////////////////////////////////////////////////////////////////////////////////////////
    for(j=0; j<routeteller; j++)
        printf("\nsplitsing[%d] is %d",j,splitsing[j]);
/////////////////This is the problem-code///////////////////////////////////////////////////////////
int routes;
routes=routeteller;
    j=0;
    while(routes)                                              ///when there are still some routes
        {
         i=0;
         while(j<true_eind)                                                ///when we're not at the end
            {
              if(splitsing[routes]==0)									///The first time, i only jump to true
                    {
                    if(workstring[j][0]==21)								///21 is the code for a test
                    j+=workstring[j][1];										///the format of workstring is [rulenumber][command],
                    }

              else if(splitsing[routes]==j)                        //when we are at a detected jumpzone
                    j+=workstring[j][2];                                ///jump to false
              else if(workstring[j][0] ==21)                            ///when there is a jump, but its not our "workingjump"
                    {
                    j+=workstring[j][1];                                ///the next commandline is at j+ truebjump
                    }
					            j++;
            mogelijke_routes[routeteller-routes][i+1]=j;	///posible_routes[routenumber][commandnumber]=the linenumber
            i++;																///for the next time, we need the next entry of mogelijke_routes
            if(workstring[j+1][0]==6)							///6 is our return, so here i now when a route ends
                break;
            }
    ////Reset the values for the new round
        routes--;
        j=0;
        }