Как сделать связанный список из бинарного дерева (до/после заказа)

Я просмотрел несколько вопросов, но я не могу понять, что происходит. Я пытаюсь преобразовать свое двоичное дерево в связанный список, который находится либо в предварительном, либо в последующем порядке. Мой код возвращает связанный список, состоящий из нулей. Я исключил код для пост-заказа, так как в данном случае он практически такой же, как и до. Вот мой соответствующий код:

typedef struct list {
    int data;
    struct list *next;
} List;

List* createNode(int data)
{
    // create node in memory
    List* list = malloc(sizeof(list));
    // init parameters
    list->data = data;
    list->next = NULL;
}

void printList(List *list)
{
    //if(list->next == NULL) printf("y");
    while(list != NULL) {
        printf("%d", list->data);
        list = list->next;
    }
}

void preOrder(node *tree, List *list)
{   
    if(tree == NULL) return;
    // visit root
    list = createNode(tree->data);
    // left
    preOrder(tree->left, list->next);
    // right
    preOrder(tree->right, list->next);
}

int preL(node *a)
{
    // create preList
    List *preList = malloc(sizeof(List));
    preOrder(a,preList);
    printList(preList);
}

c linked-list binary-tree postorder preorder
person Robert DeRienzo    schedule 01.04.2018    source источник
comment
Прежде чем кто-либо спросит, я просмотрел остальные 3 вопроса по этому поводу, они ни в малейшей степени не помогли.   -  person Robert DeRienzo    schedule 01.04.2018
comment
Что еще более важно, что в вашем MCVE (минимально воспроизводимый пример]) и его основная функция? Какие образцы данных вы используете? Что вы ожидаете? Где ваш код для печати дерева? Вы показали, что дерево построено правильно? Как выглядит структура узла? Не повреждено ли дерево после «преобразования» в список?   -  person Jonathan Leffler    schedule 01.04.2018
comment
Ах, это должно быть полным и функционирующим? Позвольте мне преобразовать его во что-то, что работает и имеет немного больше смысла.   -  person Robert DeRienzo    schedule 01.04.2018

Ответы (2)


arrow_upward
0
arrow_downward

У вас есть некоторые ошибки в понимании того, как работают списки:

  1. list* — указатель на первый элемент в списке и только на первый элемент
  2. When adding an element to the tail of the list you should loop the list in order to add the element to the back of the list. That means that you must update list->next
    • In your pre order code you are not updating the next pointer of newly created list.
    • По сути, вы переопределяете свою list переменную новым узлом, теряя все остальные узлы, обработанные до этого.

Приведенный выше метод неэффективен, потому что каждый раз, когда мы вставляем заметку, мы должны передавать все узлы в списке.

Модифицированный код:

void insertList(List *list,List *element)
{
    while(list->next != NULL) {
        printf("%d", list->data);
        list = list->next;
    }
    list->next=element;
}
void preOrder(node *tree, List *list)
{   
    if(tree == NULL) return;
    // visit root
    // the new element
    List *element = createNode(tree->data);
    //insert to the tail of the list
    insertList(list,element);
    // left
    // pass the initial list with the head inserted
    preOrder(tree->left, list);
    // right
    // pass the initial list with the head inserted and the left tree nodes
    preOrder(tree->right, list);
}

int preL(node *a)
{
    // create preList
    List *preList = malloc(sizeof(List));
    preOrder(a,preList);
    printList(preList);
}

Чтобы сделать код эффективным, вы должны НЕ зацикливать список каждый раз, когда вы вставляете элемент. Попробуйте сделать это сами!(Подсказка: вы можете сохранить указатель на последний элемент:) ).

person Paul    schedule 01.04.2018

arrow_upward
0
arrow_downward

Ваша функция выделяет только узлы, но никогда не возвращает их вызывающей стороне. Я бы написал так:

void slist_add(struct list *head, struct list **root)
{
     head->next = *root;
     *root = head;
}

struct list **preOrder(node *tree, List **list)
{   
    struct list *node;

    if (tree == NULL)
        return list;

    node = createNode(tree->data);
    slist_add(node, list);

    list = &list->next;    
    list = preOrder(tree->left, list);
    list = preOrder(tree->right, list);

    return list;
}

и назовите это как

List *preList = NULL;
preOrder(a, &preList);
person ensc    schedule 01.04.2018