Contando subárboles univales - Seguimiento

Question

Este código es una versión revisada de la implementación que solicitó un consejo de mejora. Publicación original aquí: Contando subárboles unival Créditos a: [Deduplicator], [Reinderien], [Toby Speight], [chux].

La versión revisada se aplicó siguiendo los cambios:

1. Fusionar insertRight(), insertLeft()función en createNodefunción
2. recursos gratuitos después de su uso
3. se utiliza constsi el valor de la dirección de memoria referenciada no se modifica.
4. arreglar isTreeUniv()en versión recursiva
5. deshacerse de los globales

Código revisado:

#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

Buen trabajo: es bueno ver mejoras en las reseñas que ha recibido.

Recomendaría usar lógica en &&lugar de bit a bit &en el cálculo r &node->value == parent->value. Los resultados deberían ser los mismos, pero los programadores esperan ver operadores lógicos con valores booleanos.

El cálculo de rno se puede usar &&tal cual, porque el lado derecho necesita ser evaluado por sus efectos secundarios, incluso cuando el lado izquierdo es falso. Consideraría reescribir como expresiones separadas, por lo que un futuro mantenedor no "corrige" el &para &&:

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;

Los identificadores que comienzan con isestán reservados para la extensión de la biblioteca estándar, por lo que le aconsejo que cambie el nombre isUnivSubTimpl, especialmente porque tiene un enlace externo.

No me queda claro por qué freeTree()devuelve a bool, ya que solo devuelve true.

La construcción del árbol se podría simplificar un poco con

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