Convert binary tree into simple linked list

Question

struct Monitor {
    int codMonitor;
    char* producator;
    float diagonala;
    int numarPorturi;
};

struct nodls {
    Monitor info;
    nodls* next;
};

nodls* creareNod(Monitor m) { --create node 
    nodls* nou = (nodls*)malloc(sizeof(nodls));
    nou->info.codMonitor = m.codMonitor;
    nou->info.producator = (char*)malloc(sizeof(char)*(strlen(m.producator) + 1));
    strcpy(nou->info.producator, m.producator);
    nou->info.diagonala = m.diagonala;
    nou->info.numarPorturi = m.numarPorturi;
    nou->next = nou;

    return nou;
}

nodls* inserare(nodls* cap, Monitor m) { -- insert 
    nodls* nou = creareNod(m);
    if (cap == NULL) {
        cap = nou;
        cap->next = cap;
    }
    else
    {
        nodls* temp = cap;
        while (temp->next != cap)
            temp = temp->next;
        temp->next = nou;
        nou->next = cap;
    }
    return cap;
}

void afisareMonitor(Monitor m) { -- display struct
    printf("\nMonitorul cu codul %d, producatorul %s, diagonala %f, numarul de porturi %d",
        m.codMonitor, m.producator, m.diagonala, m.numarPorturi);
}

void traversare(nodls** cap) { --display function
    nodls* temp = *cap;
    if (cap == NULL)
        printf("\nLista este goala");
    while (temp->next != *cap) {
        afisareMonitor(temp->info);
        temp = temp->next;
    }
    afisareMonitor(temp->info);

}

void stergereNod(nodls* cap) --delete node function
{
.......
}

void dezalocare(nodls* cap) { free allocate space
............
}

How I can convert using the following code, my binary tree into a simple linked list. This can be done with recursion maybe.

getLeavesList(root) {

    if root is NULL: return

    if root is leaf_node: add_to_leaves_list(root)

    getLeavesList(root -> left)

    getLeavesList(root -> right)
}

So, if the root is NULL, this is, if the function received no valid pointer, then return an error message.

If the root is a leaf, this is, if both left and right child nodes are NULL, the you have to add it to the list of leaf nodes.

Then you recursively call the function with the left and right child nodes.

Your pseudocode is almost correct, but you're only adding leaf nodes to the list, but you need to add all nodes to the list. Or do you actually want to add only the leave nodes? Your question is not very clear. — Jabberwocky

Istvan Balogh Istvan Balogh · Accepted Answer · 2020-04-30T12:16:14

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

This article covers 3 simple depth-first approaches(preorder, inorder, postorder) to traverse a binary tree. It also has a nice compact example in C.

The pseudo-code algorithm you provided is actually the proper preorder approach.

The only modification you have to make in the

void printPreorder(struct node* node)

method is to replace the printing of the node's data:

printf("%d ", node->data);

with checking if the node is a leaf and if yes adding it to a list:

if((node->left == NULL) && (node->right == NULL))
{
     appendList(&node);   
}

Of course appendList is just my ad-hoc creation but based on the code that you've provided in the question you'll know how to add to a linked-list. If not please feel free to ask.

ps: https://www.geeksforgeeks.org/ is an amazing resource hats of to those guys for the amazing work!

psps: If you'd like to return an error message when the function is called with NULL for the first time, that is if no valid tree is passed to the traversal, I'd suggest you to make a wrapper function that will call the recursive one. Then, in that wrapper you can check if the head passed to it is NULL before you even call the recursive method at all.

Convert binary tree into simple linked list

1 Answers