J'essaie de créer un algorithme de division et de conquête qui, lorsqu'il est exécuté à la racine d'un arbre binaire, renvoie la taille du plus grand sous-arbre binaire équilibré contenu dans l'arbre ou dans d'autres mots, la taille du plus grand sous-arbre possible où les feuilles sont tous à la même profondeur.Taille de la plus grande sous-arborescence binaire équilibrée
Du code pourrait vous aider. C'est Java, mais c'est assez générique.
static class Node
{
String val;
Node left, right;
}
static class MaxNode
{
Node node;
int depth;
}
static int depth(Node node)
{
if(node.left == null && node.right == null)
{
return 0;
}
else
{
return 1;
}
}
static int deepestSubtree(Node root, MaxNode maxNode)
{
if(root == null) return 0;
int depth = depth(root);
int leftDepth = deepestSubtree(root.left, maxNode);
int rightDepth = deepestSubtree(root.right, maxNode);
if(leftDepth == rightDepth)
{
depth += leftDepth;
}
if(depth > maxNode.depth)
{
maxNode.node = root;
maxNode.depth = depth;
}
return depth;
}
public static void main(String[] args)
{
Node root = buildTree();
MaxNode maxNode = new MaxNode();
deepestSubtree(root, maxNode);
if(maxNode.node == null)
{
System.out.println("No Balanced Tree");
}
else
{
int size = (int)Math.pow(2, maxNode.depth+1)-1;
System.out.format("Node: %s, Depth: %d, Size: %d\n", maxNode.node.val, maxNode.depth, size);
}
}
Pour votre exemple arbre la sortie est:
Node: D, Depth: 2, Size: 7
Un seul traversal est nécessaire: écrire une fonction récursive, qui retourne deux numéros pour un nœud: 'a': le plus grand sous-arbre équilibré vu (c'est la sortie) et 'b': si le noeud a des enfants équilibrés, retourne la profondeur. Si vous n'avez pas d'enfants équilibrés, renvoyez 0. Vous pouvez calculer 'b' pour un noeud en appelant récursivement. Si les profondeurs retournées correspondent, alors vous pouvez retourner la profondeur + 1 pour 'b', sinon zéro. Et vous devez mettre 'a' à jour avec' b'. C'est tout. – geza
Je suis désolé, je ne suis pas. Pouvez-vous élaborer plus loin? Pourquoi renvoyez-vous deux nombres pour un noeud? Pourquoi renvoyez-vous la profondeur + 1 pour b si les profondeurs retournées correspondent? Et qu'est-ce que vous mettez à jour un avec b avec? –
2 numéros sont nécessaires, car un (b) stocke la profondeur actuelle, qui peut être nulle, si le nœud est déséquilibré. Donc, un est nécessaire pour stocker le maximum actuel vu, qui ne peut pas diminuer. Par mise à jour, je veux dire un simple si: si (a
geza