Преобразование двоичного дерева в связанный список

Question

Я пытаюсь создать связанный список из двоичного дерева.

Дело в том, можно ли использовать простой связанный список вместо двусвязного списка?

Я попытался это:

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; 
} 

Конечно только часть дерева преобразуется.

Вызов в главном

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); 
} 

Спасибо you.c

Answer 1

Вот моя адаптация кода:

#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; 
} 

Я использовал назначенные инициализаторы C99, потому что вы указали компонент right перед left, который заставил меня застигнуть врасплох, и поэтому, когда я опустил назначенные инициализаторы, дерево было «назад к фронту» по сравнению с тем, что я ожидал. (Это было действительно, но не то, что я ожидал.) Обратите внимание, что я использовал статический массив для создания дерева; вам не нужно выполнять динамическое управление памятью дерева, хотя это, конечно, более условно.

Выход при выполнении кода:

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

Вы можете терпкий до форматирования, если вы хотели (%3d вместо %d будет работать).

Когда-нибудь вы должны посетить Is it a good idea to typedef pointers; короткий ответ «Нет», и все зависит от меня, я бы использовал typedef struct Tree Tree; и typedef struct List List;, а не указатель typedefs вообще.

Answer 2

Если вы пытаетесь использовать односвязный список, вы можете найти решение в ответ ниже:

https://stackoverflow.com/a/15939664/4789699