Currently I’m trying to implement different functions to realize operations on quadtrees using C language.

Context:

A quadtree (black and white picture) is:

• White
• Black
• Is broken down into 4 sub-images: top-left,top-right,bottom-left,bottom-right

Pictures are represented by the next struct:

typedef struct block_image
{
    int allBlack; //boolean
    struct block_image * son[4];
}block_image;
typedef block_image *image;

If pointer == NULL, then picture is white

If the pointer is pointing toward a struct where allBlack == true, the picture is black and son[0], son['1'], son[2] and son[3] are NULL.

If the pointer is pointing toward a struct where allBlack == false, the picture is gotten by a decomposition in 4 picture and son[0], son['1'], son[2] and son[3] are in top-left, top-right, bottom-left and bottom-right.

With this information, it is possible to implement three functions to create an image:

Build_white(): to build a white picture:

image Build_white()
{
    image newImage = NULL;
    return newImage;
}

Build_black(): to build a black picture:

image Build_black()
{
    image newImage = malloc(sizeof(block_image));
    newImage->allBlack = 1;
    newImage->son[0] = NULL;
    newImage->son[1] = NULL;
    newImage->son[2] = NULL;
    newImage->son[3] = NULL;
    return newImage;
}

Build_composed(image topL, image topR, image bottomL, image bottomR): to build a composed picture:

image Build_composed(image topL, image topR, image bottomL, image bottomR)
{
    image newImage = malloc(sizeof(block_image));
    newImage->allBlack = 0;
    newImage->son[0] = topL;
    newImage->son[1] = topR;
    newImage->son[2] = bottomL;
    newImage->son[3] = bottomR;
    return newImage;
}

Problem:

But after that, it is necessary to implement a function can print the picture, e.g white picture is represented by “W”, black picture is represented by “B” and composed picture is represented by img1img2img3img4, e.g WBBW.

So, currently, I’m trying to code this function and I pass to print black or white picture (not composed).

My current function:

void normalDisplay(image myPicture)
{
    if(myPicture == NULL)
    {
        printf("W");
    }
    else if(myPicture->allBlack == 1 && myPicture->son[0] == NULL && myPicture->son[1] == NULL && myPicture->son[2] == NULL && myPicture->son[3] == NULL)
    {
        printf("N");
    }
}

in main(): Image white1 = Build_white();

Image black1 = Build_black();

If I do normalDisplay(white1); I get “W” on the terminal, and if I do normalDisplay(black1); I get “B” on the terminal.

Else, I don’t know how to print a composed function, how to manage different possibilities on my function to can print more complex picture.

For example, this picture (course example):

can be coded like this:

image composed = Build_composed(
            Build_black(),
            Build_white(),
            Build_white(),
            Build_composed(
                Build_black(),
                Build_white(),
                Build_composed(
                    Build_white(),
                    Build_black(),
                    Build_lack(),
                    Build_white()
                ),
                Build_black()
            )
        );

And should be displayed with: BWW BW WBBWB using normalDisplay function.

So, anyone could help me to understand how I could display a composed image with a postfix notation by explaining how to modify my function so that it can consider a maximum of cases?

CodePudding user response：

how I could display a composed image with a postfix notation by explaining how to modify my function so that it can consider a maximum of cases?

That's really trivial. Just display it for this cell or display for the childs.

typedef struct block_image image;
void normalDisplay(image *t) {
    if (t == NULL) {
       printf("W"); 
    } else if (t->allBlack) {
       printf("B");
    } else {
       printf(" ");
       normalDisplay(t->son[0]);  // upper left
       normalDisplay(t->son[1]);  // upper right
       normalDisplay(t->son[2]);  // lower left
       normalDisplay(t->son[3]);  // lower right
   }
}