Liczenie jednorodnych poddrzew - kontynuacja

Nov 24 2020

Ten kod jest poprawioną wersją implementacji, która poprosiła o poradę dotyczącą ulepszeń. Oryginalny post tutaj: Zliczanie kredytów jednorodnych poddrzew do: [Deduplicator], [Reinderien], [Toby Speight], [chux].

Zmieniona wersja została zastosowana z następującymi zmianami:

  1. Scal insertRight(), insertLeft()funkcję w createNodefunkcję
  2. wolne zasoby po użyciu
  3. używany, constjeśli odwoływana wartość adresu pamięci nie jest zmieniana.
  4. naprawić isTreeUniv()w wersji rekurencyjnej
  5. pozbyć się globali

Poprawiony kod:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct stTree
{
    struct stTree *left;
    struct stTree *right;
    int value;
} stTree;

stTree* createNode(int value, stTree *leftNode, stTree *rightNode)
{
    stTree *node = malloc(sizeof *node);
    if (!node) abort();

    node->left = leftNode;
    node->right = rightNode;
    node->value = value;

    return node;
}

bool isUnivSubTimpl(const stTree *node, const stTree *parent, size_t *count)
{
    if (!node) return 1;    //node without child count as unival subT

    bool r = isUnivSubTimpl(node->left, node, count) &isUnivSubTimpl(node->right, node, count);
    *count += r;

    return (r &node->value == parent->value);
}

size_t countUnivSubT(const stTree *node)
{
    size_t count = 0;
    isUnivSubTimpl(node, node, &count);
    return count;
}

static stTree* findBottomLeft(stTree *node)
{
    while (node->left)
        node = node->left;
    return node;
}

bool freeTree(stTree *node)
{
    if (!node) return true;
    stTree *bottomLeft = findBottomLeft(node);

    while (node)
    {
        if (node->right)
        {
            bottomLeft->left = node->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }

        stTree *old = node;
        node = node->left;
        free(old);
    }
        return true;
}

int main(void)
{
    //build a tree
    stTree *rootNode =
        createNode(0,
            createNode(1, NULL, NULL),
            createNode(0,
                createNode(1,
                    createNode(1, NULL, NULL),
                    createNode(1, NULL, NULL)
               ),
                createNode(0, NULL, NULL)));

    printf("total universal subree: %u\n", countUnivSubT(rootNode));
    if (freeTree(rootNode))
        printf("memory released\n");

}

Odpowiedzi

1 TobySpeight Nov 25 2020 at 09:19

Dobra robota - miło jest widzieć ulepszenia w opiniach, które otrzymałeś.

Zalecałbym używanie do obliczeń logicznych, &&a nie bitowych . Wyniki powinny być takie same, ale programiści oczekują, że zobaczą operatory logiczne z wartościami logicznymi.&r &node->value == parent->value

Obliczenie rnie może być użyte &&tak, jak jest, ponieważ prawa strona musi zostać oceniona pod kątem skutków ubocznych, nawet jeśli lewa strona jest fałszywa. Rozważałbym przepisywanie jako oddzielne wyrażenia, więc przyszły opiekun nie „poprawia” tego &na &&:

bool l_un = isUnivSubTimpl(node->left, node, count);  /* updates *count */
bool r_un = isUnivSubTimpl(node->right, node, count); /* updates *count */
bool r = l_un && r_un;

Identyfikatory zaczynające się od issą zarezerwowane dla rozszerzenia biblioteki standardowej, więc radziłbym zmienić nazwę isUnivSubTimpl, zwłaszcza, że ​​ma ona powiązania zewnętrzne.

Nie jest dla mnie jasne, dlaczego freeTree()zwraca a bool, ponieważ zawsze zwraca true.

Budowanie drzewa można trochę uprościć dzięki

stTree *createLeafNode(int value)
{
    return createNode(value, NULL, NULL);
}