Comment déterminer si un arbre binaire est terminé?

int height (node* tree, int *max, int *min) {

  int lh = 0 , rh = 0 ;
  if ( tree == NULL )
    return 0;
  lh = height (tree->left,max,min) ;
  rh = height (tree->right,max,min) ;
  *max = ((lh>rh) ? lh : rh) + 1 ;
  *min = ((lh>rh) ? rh : lh) + 1 ;
  return *max ;
}

void isCompleteUtil (node* tree, int height, int* finish, int *complete) {
  int lh, rh ;
  if ( tree == NULL )
    return ;
  if ( height == 2 ) {
    if ( *finish ) {
      if ( !*complete )
        return;
      if ( tree->left || tree->right )
        *complete = 0 ;
      return ;
    }
    if ( tree->left == NULL && tree->right != NULL ) {
      *complete = 0 ;
      *finish = 1 ;
    }
    else if ( tree->left == NULL && tree->right == NULL )
      *finish = 1 ;
    return ;
  }
  isCompleteUtil ( tree->left, height-1, finish, complete ) ;
  isCompleteUtil ( tree->right, height-1, finish, complete ) ;
}

int isComplete (node* tree) {
  int max, min, finish=0, complete = 1 ;
  height (tree, &max, &min) ;
  if ( (max-min) >= 2 )
    return 0 ;
  isCompleteUtil (tree, max, &finish, &complete) ;
  return complete ;
}

Le code suivant traite simplement tous les cas possibles. La hauteur de l'arbre est obtenue en cours de route pour éviter une autre récursion.

enum CompleteType
{
    kNotComplete = 0,
    kComplete = 1, // Complete but not full
    kFull = 2,
    kEmpty = 3
};

CompleteType isTreeComplete(Node* node, int* height)
{
    if (node == NULL)
    {
        *height = 0;
        return kEmpty;
    }

    int leftHeight, rightHeight;

    CompleteType leftCompleteType = isTreeComplete(node->left, &leftHeight);
    CompleteType rightCompleteType = isTreeComplete(node->right, &rightHeight);

    *height = max(leftHeight, rightHeight) + 1;

    // Straight forwardly treat all possible cases
    if (leftCompleteType == kComplete && 
        rightCompleteType == kEmpty &&
        leftHeight == rightHeight + 1)
        return kComplete;

    if (leftCompleteType == Full)
    {
        if (rightCompleteType == kEmpty && leftHeight == rightHeight + 1)
            return kComplete;
        if (leftHeight == rightHeight)
        {
            if (rightCompleteType == kComplete)
                return kComplete;
            if (rightCompleteType == kFull)
                return kFull;
        }
    }

    if (leftCompleteType == kEmpty && rightCompleteType == kEmpty)
        return kFull;

    return kNotComplete;
}

bool isTreeComplete(Node* node)
{
    int height;
    return (isTreeComplete(node, &height) != kNotComplete);
}

Vous pouvez également résoudre ce problème en utilisant la traversée de commande de commande. La procédure est la suivante:

1. Stockez l'élément de données des nœuds rencontrés dans un vecteur
2. Si le nœud est NULL, puis stockez un numéro spécial (INT_MIN)
3. Gardez une trace du dernier nœud non nul visité - LenteTry
4. Maintenant, traversez le vecteur jusqu'à l'autre détenteur. Si vous rencontrez jamais INT_MIN, l'arborescence n'est pas terminée. Sinon c'est un arbre binaire complet.

   Voici un code C ++:

   mon nœud d'arbre est: xxx

private static boolean isCompleteBinaryTree(TreeNode root) {

if (root == null) {
    return false;
} else {
    boolean completeFlag = false;
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(root);
    while (!list.isEmpty()) {
        TreeNode element = list.remove(0);
        if (element.left != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.left);
        } else {
            completeFlag = true;
        }
        if (element.right != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.right);
        } else {
            completeFlag = true;
        }
    }
        return true;
    }
}
Reference:
Check the following link for a detailed explanation
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Merci pour le pseudo code de @jonathan Graehl. Je l'ai mis en œuvre à Java. Je l'ai testé contre la version itérative. Cela fonctionne comme un charme!

public static boolean isCompleteBinaryTreeRec(TreeNode root){
//      Pair notComplete = new Pair(-1, false);
//      return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);
    return isCompleteBinaryTreeSubRec(root).height != -1;
}

public static boolean isPerfectBinaryTreeRec(TreeNode root){
    return isCompleteBinaryTreeSubRec(root).isFull;
}

public static Pair isCompleteBinaryTreeSubRec(TreeNode root){
    if(root == null){
        return new Pair(0, true);
    }

    Pair left = isCompleteBinaryTreeSubRec(root.left);
    Pair right = isCompleteBinaryTreeSubRec(root.right);

    if(left.isFull && left.height==right.height){
        return new Pair(1+left.height, right.isFull);
    }

    if(right.isFull && left.height==right.height+1){
        return new Pair(1+left.height, false);
    }

    return new Pair(-1, false);
}

private static class Pair{
    int height;         
    boolean isFull;     

    public Pair(int height, boolean isFull) {
        this.height = height;
        this.isFull = isFull;
    }

    public boolean equalsTo(Pair obj){
        return this.height==obj.height && this.isFull==obj.isFull;
    }
}

Voici un code C pour vérifier si l'arborescence binaire est terminée: xxx

la manière dont il fonctionne est:

• Si la profondeur de la sous-arbre gauche est la même que la profondeur du sous-arbre de droite, il retourne la profondeur de l'Hireearchy.

• Si la profondeur de la sous-arbre gauche est une plus grande que la profondeur du sous-arbre droit, il retourne la profondeur de la sous-étude droite en haut de l'hirarchie et active le drapeau.

• S'il trouve que la profondeur de la sous-arbre gauche et du sous-arbre et du drapeau droit est déjà définie, il renvoie -1 up la hiérarchie.

• à la fin, si la fonction renvoie -1, ce n'est pas le sous-arbre complet, sinon la valeur renvoyée est la profondeur minimale de l'arborescence.

pour qu'un arbre soit complet

hauteur (gauche) == hauteur (à droite) ou Hauteur (à gauche) == 1 + hauteur (droite) xxx

bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }
please consider as a correct answer if you found useful.

Tout d'abord, comptez le nombre de nœuds dans l'arbre binaire. Écrivez une fonction récursive. Si le nœud reçu est NULL, cela revient vrai. Si l'index du nœud est supérieur ou égal de nœuds, l'arborescence n'est pas binaire. Si aucun de ces deux est arrivé, vérifiez les sous-arbres gauche et droit. import java.util.linkedlist; import java.util.queue; xxx

J'espère que cela aide.