c - 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
");
         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 
", height(clone));

    print_t(tree);

    plist(l);
}

Thank you.c

Answer 1

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
");
        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
", (void *)tree);
    print_tree_inorder_recursive(tree);
    putchar('
');
}

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

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.