CODEWITHSUNDEEP
cpointersdata-structuresbinary-tree
J.Gomes
J.Gomes

Reputation: 1

How does this C code reverse the binary tree in situ?

I've been asked by my teachers to write a function in C that mirrors a binary tree, and by that I mean that inverts the tree. I've been struggling with this question because the solution doesn't make any sense to me. The data struct we use is the following:

typedef struct nodo {

  int valor;

  struct nodo *esq, *dir;
} *ABin;

and the solution is:

void mirror (ABin *a) {

    ABin c = *a;
   if (c == NULL);

    else {
        ABin e = c -> esq;
        ABin d = c -> dir;
        c -> esq = d;
        c -> dir = e;
        mirror (&(c -> esq));
        mirror (&(c -> dir)); 
    }
}

My biggest concern here is the use of pointers or not. I don't understand why, when we call the function recursively, we have to use & when esq and dir are already pointers to the struct nodo type?

Upvotes: 0

Views: 309

Answers (4)

jschultz410
jschultz410

Reputation: 2899

The higher level answer to your question is that by recursively swapping every node's left and right subtrees, you reverse the tree's ordering invariant.

Typically, a binary search tree maintains the invariant that every left descendant orders earlier (or equal to) than the current node, while every right descendant orders later (or equal to) the current node according to the ordering function of the tree. By swapping the left and right subtrees at every node in the tree, you reverse the ordering invariant of the tree.

As to your question about the level of pointer indirection, there is no good reason for the mirror function to take an ABIN pointer. It should just take an ABIN as that is a pointer to a tree node by typedef. Even better, you (or your teachers) wouldn't make a typedef for a pointer to a struct in the first place without good reason.

Upvotes: 1

Cioaca Radu
Cioaca Radu

Reputation: 88

As you can see esq and dir are pointers to a struct nodo.

Using the typedef struct nodo{} *ABin makes ABin type also a pointer to a struct nodo.

so

ABin is equivalent to struct nodo * (types).

So, for your function void mirror (ABin *a), a would be a pointer to a pointer.

parameter a  is struct nodo** // pointer to a  pointer

Your function must modify the pointer itself so you must pass its address; that's why you call the function with &.

Upvotes: 0

ikegami
ikegami

Reputation: 386406

You are making a typedef for a pointer.

 typedef struct nodo* ABin;

This is asking for confusion! In fact, it seemed to have confused you because

void mirror(ABin*)

is the same as

void mirror(struct nodo**)

and there's no reason for that extra layer of indirection. You could change that to

void mirror(ABin)

but it's best to avoid making typedefs for pointers in the first place.

Cleaned up:

typedef struct Nodo {
    int valor;
    struct Nodo* esq;
    struct Nodo* dir;
} Nodo;

void mirror(Nodo* nodo) {
    if (nodo == NULL)
        return;

    Nodo* tmp = nodo->esq;
    nodo->esq = nodo->dir;
    nodo->dir = tmp;

    mirror(nodo->esq);
    mirror(nodo->dir); 
}

Upvotes: 0

wildplasser
wildplasser

Reputation: 44250

You only need to swap the pointers (even if one of them is NULL)

struct node {
        struct node *prev;
        struct node *next;
        int key;
        char payload[123];
        };

void mirror(struct node *ptr)
{
struct node *tmp;

if (!ptr) return;

tmp = node->prev;
node->prev = node->next;
node->next= tmp;

mirror(node->prev);
mirror(node->next);
}

Upvotes: 0

Related Questions