¿Cómo determinar si un árbol binario está completo?

Question

Un árbol binario completo se define como un árbol binario en el que cada nivel, excepto posiblemente el más profundo, está completamente lleno. En el nivel más profundo, todos los nodos deben estar lo más a la izquierda posible.

Creo que un algoritmo recursivo simple podrá decir si un árbol binario dado está completo, pero parece que no puedo resolverlo.

Answer 1

similares a:

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right)) 

Usted tiene:

perfect(t) = if (t==NULL) then 0 else { 
        let h=perfect(t.left) 
        if (h != -1 && h==perfect(t.right)) then 1+h else -1 
      } 

Dónde perfecta (t) devuelve -1 si las hojas no son todos a la misma profundidad, o cualquier nodo tiene un solo niño; de lo contrario, devuelve la altura.

Editar: se trata de "completo" = "Un árbol binario perfecto es un árbol binario completo en el que todas las hojas están a la misma profundidad o mismo nivel 1 (Esta ambigüedad también se llama un árbol binario completo.)." (Wikipedia).

Aquí hay una comprobación recursiva de: "Un árbol binario completo es un árbol binario en el que cada nivel, excepto posiblemente el último, está completamente lleno, y todos los nodos están lo más a la izquierda posible". Devuelve (-1, falso) si el árbol no está completo; de lo contrario (alto, lleno) si lo está, con == verdadero verdadero si es perfecto.

complete(t) = if (t==NULL) then (0,true) else { 
        let (hl,fl)=complete(t.left) 
        let (hr,fr)=complete(t.right)      
        if (fl && hl==hr) then (1+h,fr) 
        else if (fr && hl==hr+1) then (1+h,false) 
        else (-1,false) 
       } 

Answer 2

Se puede combinar tres piezas de información a partir de los subárboles:

• si el subárbol es completa

• La altura máxima

• La altura mínima (equivalente a la máxima altura o altura máxima - 1)

Answer 3

Puede decir si un árbol binario dado es un árbol binario izquierdo completo, mejor conocido como montón binario, asegurándose de que cada nodo con un niño derecho también tenga un niño izquierdo. Véase más adelante

bool IsLeftComplete(tree) 
{ 

    if (!tree.Right.IsEmpty && tree.Left.IsEmpty) 
    //tree has a right child but no left child, therefore is not a heap 
    return false;  

    if (tree.Right.IsEmpty && tree.Left.IsEmpty) 
    //no sub-trees, thus is leaf node. All leaves are complete 
    return true; 

    //this level is left complete, check levels below 
    return IsLeftComplete(tree.Left) && IsLeftComplete(tree.Right); 
} 

Answer 4

Puede haber un posible algoritmo que me siento resolvería este problema. Considere el árbol:

Level 0: a 
Level 1: b c 
Level 2: d e f g 

• Empleamos primero en amplitud de recorrido.

• Para cada elemento en cola en la cola de lo que tenemos que hacer tres cheques en orden:

  1. Si hay un solo niño o niña sin terminar; else, marque 2.
  2. Si existen ambos hijos configure un indicador global = verdadero.
     1. Establecer banderas para cada nodo en la cola como verdadero: flag [b] = flag [c] = true.
     2. Revise cada entrada si se han salido de n derecho niño n luego configure las banderas o restablezca a falso.
     3. (Quitar de la cola) si (queue_empty())
        comparar todas las banderas de los ganglios [...] si todo es verdad global_flag = true demás global_flag = false.
     4. Si global_flag = true ir para proceder con el siguiente nivel de amplitud primero recorrido demás terminan

Ventaja: árbol entero no puede ser atravesada
de arriba: el mantenimiento de las entradas de la bandera

Answer 5

Puedes hacerlo recursivamente comparando las alturas de los hijos de cada nodo. Puede haber como máximo un nodo donde el niño izquierdo tiene una altura exactamente uno mayor que el niño correcto; todos los demás nodos deben estar perfectamente equilibrados.

Answer 6

//Author : Sagar T.U, PESIT 
//Helper function 

int depth (struct tree * n) 
{ 
    int ld,rd; 

    if (n == NULL) return 0; 

    ld=depth(n->left); 
    ld=depth(n->right); 

    if (ld>rd) 
     return (1+ld); 
    else 
     return (1+rd); 

} 


//Core function 

int isComplete (struct tree * n) 
{ 
    int ld,rd; 

    if (n == NULL) return TRUE; 

    ld=depth(n->left); 
    rd=depth(n->right); 

    return(ld==rd && isComplete(n->left) && isComplete(n->right)); 

} 

Answer 7

El procedimiento más sencillo es:

1. Búsqueda profundidad del árbol (algoritmo sencillo).
2. Cuenta el número de nodos en un árbol (atravesando e incrementando el contador en uno al visitar cualquier nodo).
3. Para un árbol binario completo de nivel d número de nodos es igual a pow (2, d + 1) -1.

Si la condición satisface el árbol, es árbol binario completo, sino no.

Ese es un algoritmo simple y convertirlo en un código de trabajo no debería ser un problema si usted es lo suficientemente bueno como codificador.

Answer 8

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 ; 
} 

Answer 9

El siguiente código simplemente trata todos los casos posibles. La altura del árbol se obtiene a lo largo del camino para evitar otra recursión.

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); 
} 

Answer 10

También puede resolver este problema mediante el uso de recorrido de fin de nivel. El procedimiento es el siguiente:

1. tienda el elemento de datos de los nodos se encuentran en un vector
2. Si el nodo es NULL, a continuación, almacenar un número especial (INT_MIN)
3. perder de vista el pasado no nodo nulo visitado - latencia
4. Ahora recorra el vector hasta latencia. Si alguna vez encuentras INT_MIN, entonces el árbol no está completo. De lo contrario, es un árbol binario completo.

Aquí hay un código C++:

Mi nodo del árbol es:

struct node{ 
    int data; 
    node *left, *right; 
}; 

void checkcomplete(){//checks whether a tree is complete or not by performing level order traversal 
    node *curr = root; 
    queue<node *> Q; 
    vector<int> arr; 
    int lastentry = 0; 
    Q.push(curr); 
    int currlevel = 1, nextlevel = 0; 
    while(currlevel){ 
     node *temp = Q.front(); 
     Q.pop(); 
     currlevel--; 
     if(temp){ 
      arr.push_back(temp->data); 
      lastentry = arr.size(); 
      Q.push(temp->left); 
      Q.push(temp->right); 
      nextlevel += 2; 
     }else 
      arr.push_back(INT_MIN); 
     if(!currlevel){ 
      currlevel = nextlevel; 
      nextlevel = 0; 
     } 
    } 
    int flag = 0; 
    for(int i = 0; i<lastentry && !flag; i++){ 
     if(arr[i] == INT_MIN){ 
      cout<<"Not a complete binary tree"<<endl; 
      flag = 1; 
     } 
    } 
    if(!flag) 
     cout<<"Complete binary tree\n"; 
} 

Answer 11

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; 
    } 
} 

Referencia: Compruebe el siguiente enlace para una explicación detallada http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Answer 12

Gracias por El pseudo código de Jonathan Graehl. Lo he implementado en Java. Lo he probado contra la versión iterativa. ¡Funciona a las mil maravillas!

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; 
    } 
} 

Answer 13

Aquí es un código C para comprobar si el árbol binario es completa:

struct node 
{ 
    int data; 
    struct node * left; 
    struct node * right; 
}; 
int flag; 
int isComplete(struct node *root, int depth) 
{ 
    int ld, rd; 
    if (root==NULL) return depth; 
    else 
    { 
     ld = isComplete(root->left,depth+1); 
     rd = isComplete(root->right, depth+1); 
     if (ld==-1 || rd==-1) return -1; 
     else if (ld==rd) return ld; 
     else if (ld==rd-1 && flag==0) 
     { 
      flag=1; 
      return rd; 
     } 
     else return -1; 
    } 
} 

La forma en que funciona es:

• Si la profundidad del subárbol izquierdo es igual que profundidad del subárbol derecho, devuelve la profundidad de la armería.

• si la profundidad del subárbol izquierdo es una más que la profundidad del subárbol derecho, devuelve la profundidad del subárbol derecho hasta la hirarquía y habilita el indicador.

• Si encuentra que la profundidad del subárbol izquierdo y del subárbol y bandera derecha ya está establecido, devuelve -1 en la jerarquía.

• Al final, si la función devuelve -1, no es el subárbol completo, de lo contrario, el valor devuelto es la profundidad mínima del árbol.