Convert binary tree to linked list

Question

I am trying to create a linked list from a binary tree.

The thing is, is it possible to use a simple linked list instead of the doubly linked list?

I tried this:

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;


typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

void preorder(ABin tree, SList *l)
{

    if(tree)
        {
         (*l)->value = tree->value;
         (*l)->next = (SList) malloc(sizeof(struct slist));
         l = &((*l)->next);
         printf("tese\n");
         preorder(tree->left, l);
         preorder(tree->right, l);
        }
    return;
}

Of course only a part of the tree is converted.

Calling in the main

int main(){
    SList l = (SList) malloc(sizeof(struct slist));
    preorder(tree, &l);

    SList l = (SList) malloc(sizeof(struct slist));
    preorder(tree, &l);

    printf("height tree. %d \n", height(clone));

    print_t(tree);

    plist(l);
}

Thank you.c

Of course it is possible to use a singular linked list instead of a doubly linked list. Why wouldn't it? The problem is not in the data structure but your implementation of the traversal. For example, the same `l` value is being passed to both the left and right traversals. And it's not clear what the intent of mallocing `next->next` is as it does not appear to be used. — kaylum, Jul 07 '15 at 04:26
@AlanAu Sorry that was on one of my attempts to modify the code, removed that line. Yeah, the code is flawed, just showing that i have tried something eheh. Not just asking for help before trying by myself — skills, Jul 07 '15 at 05:11
While your `main()` is admirably minimal, the acronym MCVE ([How to create a Minimal, Complete, and Verifiable Example?](http://stackoverflow.com/help/mcve)) includes the term 'complete', and your code doesn't show a tree that's created, so there's nothing to convert into a list. Your problem is that after you've crawled down the left side of the tree below a node, you don't adjust `l` to point to the end of what was found, so the right side of the tree overwrites what the left did. You need to look at how you insert nodes into the list. I recommend using a separate function for the task. — Jonathan Leffler, Jul 07 '15 at 05:16
@JonathanLeffler I did minimized the code to what was relevant, i have 2 functions, one draws a tree, the other prints the linked list. — skills, Jul 07 '15 at 05:25
You did a great job on the minimization; unfortunately, you forgot about the completeness. — Jonathan Leffler, Jul 07 '15 at 05:39
@JonathanLeffler i added the rest of the main, where i confirm the results. — skills, Jul 07 '15 at 05:42
With all due respect, you've not shown how `tree` is declared or initialized, nor have you shown `height()` or `print_t()` or `plist()`. These are relevant to a complete example. Well, I'm not sure that the height is necessary. It is a good idea to print the tree, and it is also a good idea to print the list. See my example code for what I think is relevant. Recursive tree printing is messy if you don't print one node per line; you have to know when you've reached the end. I used a non-recursive wrapper around a recursive function for the task; it's one way to deal with it. — Jonathan Leffler, Jul 07 '15 at 05:46

score 3 · Accepted Answer · edited May 23 '17 at 12:01

Here's my adaptation of your code:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

static void insert(SList *l, int value)
{
    assert(l != 0);
    SList node = malloc(sizeof(*node));
    if (node == 0)
    {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = *l;
    *l = node;
}

static void preorder(ABin tree, SList *l)
{
    if (tree)
    {
         insert(l, tree->value);
         preorder(tree->left, l);
         preorder(tree->right, l);
    }
}

static arvb test_tree[] =
{
    { .value = 19,  .left = &test_tree[2], .right = &test_tree[5] },    /*0*/
    { .value = 11,  .left =             0, .right =             0 },    /*1*/
    { .value = 13,  .left = &test_tree[1], .right = &test_tree[3] },    /*2*/
    { .value = 17,  .left =             0, .right =             0 },    /*3*/
    { .value = 101, .left =             0, .right =             0 },    /*4*/
    { .value = 103, .left = &test_tree[4], .right = &test_tree[6] },    /*5*/
    { .value = 107, .left =             0, .right = &test_tree[7] },    /*6*/
    { .value = 109, .left =             0, .right =             0 },    /*7*/
};

static void print_tree_inorder_recursive(arvb *tree)
{
    if (tree)
    {
        print_tree_inorder_recursive(tree->left);
        printf(" %d", tree->value);
        print_tree_inorder_recursive(tree->right);
    }
}

static void print_tree_inorder(arvb *tree)
{
    printf("Tree: %p\n", (void *)tree);
    print_tree_inorder_recursive(tree);
    putchar('\n');
}

static void print_list(SList list)
{
    while (list != 0)
    {
        printf(" %d", list->value);
        list = list->next;
    }
    putchar('\n');
}

int main(void)
{
    SList l = 0;
    print_tree_inorder(test_tree);
    preorder(test_tree, &l);
    print_list(l);
    return 0;
}

I've used C99 designated initializers because you listed the right component before the left, which caught me unawares, and when I omitted the designated initializers, therefore, the tree was 'back to front' compared with what I expected. (It was valid, but not what I expected.) Note that I've used a static array to create the tree; you don't have to do dynamic memory management of the tree, though it is certainly more conventional to do so.

The output when the code is run:

Tree: 0x101df5060
 11 13 17 19 101 103 107 109
 109 107 101 103 17 11 13 19

You could tart up the formatting if you wished (%3d instead of %d would work).

Sometime, you should visit Is it a good idea to typedef pointers; the short answer is 'No' and were it up to me, I'd be using typedef struct Tree Tree; and typedef struct List List; and not the pointer typedefs at all.

Convert binary tree to linked list

1 Answers1

Linked