Конвертировать двоичное дерево в простой связанный список - PullRequest
Новая
       70

Конвертировать двоичное дерево в простой связанный список

0 голосов
/ 30 апреля 2020 
struct Monitor {
    int codMonitor;
    char* producator;
    float diagonala;
    int numarPorturi;
};

struct nodls {
    Monitor info;
    nodls* next;
};

nodls* creareNod(Monitor m) { --create node 
    nodls* nou = (nodls*)malloc(sizeof(nodls));
    nou->info.codMonitor = m.codMonitor;
    nou->info.producator = (char*)malloc(sizeof(char)*(strlen(m.producator) + 1));
    strcpy(nou->info.producator, m.producator);
    nou->info.diagonala = m.diagonala;
    nou->info.numarPorturi = m.numarPorturi;
    nou->next = nou;

    return nou;
}

nodls* inserare(nodls* cap, Monitor m) { -- insert 
    nodls* nou = creareNod(m);
    if (cap == NULL) {
        cap = nou;
        cap->next = cap;
    }
    else
    {
        nodls* temp = cap;
        while (temp->next != cap)
            temp = temp->next;
        temp->next = nou;
        nou->next = cap;
    }
    return cap;
}

void afisareMonitor(Monitor m) { -- display struct
    printf("\nMonitorul cu codul %d, producatorul %s, diagonala %f, numarul de porturi %d",
        m.codMonitor, m.producator, m.diagonala, m.numarPorturi);
}

void traversare(nodls** cap) { --display function
    nodls* temp = *cap;
    if (cap == NULL)
        printf("\nLista este goala");
    while (temp->next != *cap) {
        afisareMonitor(temp->info);
        temp = temp->next;
    }
    afisareMonitor(temp->info);

}

void stergereNod(nodls* cap) --delete node function
{
.......
}

void dezalocare(nodls* cap) { free allocate space
............
}

Как я могу преобразовать, используя следующий код, мое двоичное дерево в простой связанный список. Это может быть сделано с помощью рекурсии. 

getLeavesList(root) {

    if root is NULL: return

    if root is leaf_node: add_to_leaves_list(root)

    getLeavesList(root -> left)

    getLeavesList(root -> right)
}

Итак, если root равно NULL, то это если функция не получила действительного указателя, а затем вернуть сообщение об ошибке.

Если root является листом, то есть, если левый и правый дочерние узлы имеют значение NULL, его необходимо добавить в список листовых узлов.

Затем вы рекурсивно вызываете функцию с левым и правым дочерними узлами.

1 Ответ

0 голосов
/ 30 апреля 2020

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

В этой статье рассматриваются 3 простых подхода, основанных на глубине (предварительный порядок, порядок, последующий порядок) для обхода двоичного дерева. У этого также есть хороший компактный пример в C.

Алгоритм псевдокода, который вы предоставили, на самом деле является правильным подходом предварительного заказа.

Единственная модификация, которую вы должны сделать в

void printPreorder(struct node* node)

метод заключается в замене печати данных узла:

printf("%d ", node->data);

проверкой, является ли узел листом, и, если да, добавлением это к списку: 

if((node->left == NULL) && (node->right == NULL))
{
     appendList(&node);   
}

Конечно appendList - это просто мое ad-ho c создание, но на основе кода, который вы предоставили в вопросе, вы будете знать, как добавить к связанный список. Если нет, пожалуйста, не стесняйтесь спрашивать.

ps: https://www.geeksforgeeks.org/ - это потрясающий ресурс для тех ребят, которые за потрясающую работу!

psps: Если вы ' Я хотел бы вернуть сообщение об ошибке, когда функция вызывается с NULL в первый раз, то есть, если в обход не передано действительное дерево, я бы предложил вам создать функцию-обертку, которая будет вызывать рекурсивную. Затем в этой оболочке вы можете проверить, равна ли переданная ему голова NULL, прежде чем вы вообще вызовете рекурсивный метод.

...