Comptage des sous-arbres univaux - Suivi
Ce code est une version révisée de l'implémentation qui demandait un avis d'amélioration. Message original ici: Comptage des sous-arbres unival Crédits à: [Deduplicator], [Reinderien], [Toby Speight], [chux].
La version révisée a été appliquée suite aux modifications:
- Fusionner la
insertRight(), insertLeft()
fonction encreateNode
fonction - ressources gratuites après utilisation
- utilisé
const
si la valeur de l'adresse mémoire référencée n'est pas modifiée. - correction
isTreeUniv()
en version récursive - se débarrasser des globaux
Code révisé:
#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");
}
Réponses
Bon travail - c'est agréable de voir les améliorations que vous avez reçues.
Je recommanderais d'utiliser logique &&
plutôt que bit &
à bit dans le calcul r &node->value == parent->value
. Les résultats doivent être identiques, mais les programmeurs s'attendent à voir des opérateurs logiques avec des valeurs booléennes.
Le calcul de r
ne peut pas être utilisé &&
tel quel, car le côté droit doit être évalué pour ses effets secondaires, même lorsque le côté gauche est faux. Je considérerais la réécriture comme des expressions séparées, donc un futur responsable ne "corrige" pas le &
to &&
:
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;
Les identifiants commençant par is
sont réservés à l'extension Standard Library, je vous conseille donc de changer le nom isUnivSubTimpl
, d'autant plus qu'il a un lien externe.
Je ne vois pas pourquoi je freeTree()
renvoie un bool
, car il ne revient que jamais true
.
Construire l'arbre pourrait être un peu simplifié avec
stTree *createLeafNode(int value)
{
return createNode(value, NULL, NULL);
}