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
– kaylum, Commented Jul 7, 2015 at 4: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
– skills, Commented Jul 7, 2015 at 5:11
While your main() is admirably minimal, the acronym MCVE (How to create a Minimal, Complete, and Verifiable Example?) 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
– Jonathan Leffler, Commented Jul 7, 2015 at 5: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
– skills, Commented Jul 7, 2015 at 5:25

Community · Accepted Answer · 2017-05-23 12:01:57Z

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.

Collectives™ on Stack Overflow

Convert binary tree to linked list

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related