Contando subárvores unival - Acompanhamento

Question

Este código é uma versão revisada da implementação que solicitou um conselho sobre melhorias. Postagem original aqui: Contando subárvores unival Créditos para: [Deduplicator], [Reinderien], [Toby Speight], [chux].

A versão revisada foi aplicada após as alterações:

1. Mesclar insertRight(), insertLeft()função em createNodefunção
2. recursos livres após o uso
3. usado constse o valor do endereço de memória referenciado não for alterado.
4. corrigir isTreeUniv()em versão recursiva
5. livrar-se dos globais

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

Bom trabalho - é bom ver melhorias nas avaliações que você recebeu.

Eu recomendaria usar lógico em &&vez de bit a bit &na computação r &node->value == parent->value. Os resultados devem ser os mesmos, mas os programadores esperam ver operadores lógicos com valores booleanos.

O cálculo de rnão pode ser usado &&como está, porque o lado direito precisa ser avaliado quanto aos seus efeitos colaterais, mesmo quando o lado esquerdo é falso. Eu consideraria reescrever como expressões separadas, para que um futuro mantenedor não "corrija" o &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;

Os identificadores que começam com issão reservados para a extensão da Biblioteca Padrão, portanto, aconselho alterar o nome isUnivSubTimpl, principalmente porque ele tem uma ligação externa.

Não está claro para mim por que freeTree()retorna um bool, já que ele sempre retorna true.

Construir a árvore pode ser um pouco simplificado com

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