Zählen von univalen Teilbäumen - Follow Up

Question

Dieser Code ist eine überarbeitete Version der Implementierung, in der um Verbesserungsvorschläge gebeten wurde. Originaler Beitrag hier: Zählen von univalen Teilbäumen Credits an: [Deduplikator], [Reinderien], [Toby Speight], [chux].

Die überarbeitete Version wurde nach folgenden Änderungen angewendet:

1. Merge - insertRight(), insertLeft()Funktion in createNodeFunktion
2. freie Ressourcen nach Gebrauch
3. constWird verwendet, wenn der Wert der referenzierten Speicheradresse nicht geändert wird.
4. Fix isTreeUniv()in rekursive Version
5. Globale loswerden

Überarbeiteter Code:

#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");

}

Answer 1

Gute Arbeit - es ist schön, Verbesserungen gegenüber den Bewertungen zu sehen, die Sie erhalten haben.

Ich würde empfehlen, bei der Berechnung &&eher logisch als bitweise &zu verwenden r &node->value == parent->value. Die Ergebnisse sollten gleich sein, aber Programmierer erwarten logische Operatoren mit booleschen Werten.

Die Berechnung von rkann nicht so verwendet werden, &&wie sie ist, da die rechte Seite auf ihre Nebenwirkungen untersucht werden muss, selbst wenn die linke Seite falsch ist. Ich würde das Umschreiben als separate Ausdrücke betrachten, damit ein zukünftiger Betreuer das &to nicht "korrigiert" &&:

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;

Bezeichner, die mit beginnen, issind für die Standardbibliothekserweiterung reserviert. Daher würde ich empfehlen, den Namen zu ändern isUnivSubTimpl, insbesondere da er über eine externe Verknüpfung verfügt.

Mir ist nicht klar, warum freeTree()a zurückgegeben wird bool, da es immer nur zurückkehrt true.

Das Bauen des Baumes könnte ein wenig vereinfacht werden

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