recorrido - programar un arbol binario de busqueda en java

Cuenta de nodos en un árbol en Java

Question

Antes que nada, juro que esto no es tarea, es una pregunta que me hicieron en una entrevista. Creo que lo hice un lío (aunque me di cuenta de que la solución requiere recursividad). Aquí está la pregunta:

Implemente el método count () que devuelve la cantidad de nodos en un árbol. Si un nodo no tiene un hijo izquierdo o derecho, el método getXXChild() relevante devolverá null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

Mi razón para hacer la pregunta es simplemente curiosidad por ver la solución correcta y, por lo tanto, medir cuán mala era la mía.

Saludos, Tony

Answer 1

Algo como esto debería funcionar:

int count()
{
    int left = getLeftChild() == null ? 0 : getLeftChild().count();
    int right = getRightChild() == null ? 0 : getRightCHild().count();

    return left + right + 1;
}

Answer 2

Este es un problema de recursión estándar:

count():
    cnt = 1 // this node
    if (haveRight) cnt += right.count
    if (haveLeft)  cnt += left.count
return cnt;

Muy ineficiente, y un asesino si el árbol es muy profundo, pero eso es recurrencia para ti ...

Answer 3

Implementa el método:

public static int countOneChild(Node root)
{
    ...
}

eso cuenta la cantidad de nodos internos en un árbol binario que tiene un hijo. Agregue la función al programa tree.java .

Answer 4

Las preguntas relacionadas con el árbol binario deben esperarse en una entrevista. Yo diría que tome un tiempo antes de cualquier próxima entrevista y vaya a través de this enlace. Hay aproximadamente 14 problemas resueltos. Puede echar un vistazo y ver cómo se hace la solución. Esto le daría una idea de cómo abordar un problema con el árbol binario en el futuro.

Sé que su pregunta es específica para el método de recuento. También se implementó en el enlace que brindé

Answer 5

Lo hice por preorden recurssion. A pesar de que no sigue exactamente el formato de la entrevista con el uso de localRoot, pero creo que entiendes la idea.

private int countNodes(Node<E> localRoot, int count) {
    if (localRoot == null) 
        return count;     
    count++; // Visit root
    count = countNodes(localRoot.left, count); // Preorder-traverse (left)
    count = countNodes(localRoot.right, count); // Preorder-traverse (right)
    return count;
}

public int countNodes() {
   return countNodes(root, 0);
}

Answer 6

Me gusta más porque dice:

recuento de vueltas para el conteo izquierdo + para el derecho + 1

  int count() {
      return  countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
  }
  private int countFor( Tree tree )  { 
       return tree == null ? 0 : tree.count();
  }

Un poco más hacia la programación alfabetizada.

Por cierto, no me gusta la convención de getter / setter que se usa tan comúnmente en Java, creo que un uso de leftChild () sería mejor:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1;

Al igual que Hoshua Bloch, explica aquí http://www.youtube.com/watch?v=aAb7hSCtvGw en mín. 32:03

Si lo logras, tu código dice ...

PERO, tengo que admitir que la convención get / set es ahora casi parte del lenguaje. :)

Para muchas otras partes, seguir esta estrategia crea un código de auto documentación, que es algo bueno.

Tony: Me pregunto, ¿cuál fue tu respuesta en la entrevista?

Answer 7

Mi primer intento no tenía nada nuevo que agregar, pero luego empecé a preguntarme acerca de la profundidad de la recursión y si sería posible reordenar el código para aprovechar la función de optimización de llamada final del último compilador de Java. El principal problema fue la prueba nula, que se puede resolver usando un objeto Null. No estoy seguro si TCO puede manejar ambas llamadas recursivas, pero al menos debería optimizar la última.

static class NullNode extends Tree {

    private static final Tree s_instance = new NullNode();

    static Tree instance() {
        return s_instance;
    }

    @Override
    Tree getRightChild() {  
        return null;
    }  

    @Override
    Tree getLeftChild() {  
        return null;
    }  

    int count() {  
        return 0;
    }
}

int count() {      
    Tree right = getRightChild();      
    Tree left  = getLeftChild();      

    if ( right == null ) { right = NullNode.instance(); }
    if ( left  == null ) { left  = NullNode.instance(); }

    return 1 + right.count() + left.count();
}   

La implementación precisa de NullNode depende de las implementaciones utilizadas en Tree: si Tree usa NullNode en lugar de null, quizás los métodos de acceso secundario deberían arrojar NullPointerException en lugar de devolver null. De todos modos, la idea principal es usar un NullObject para intentar beneficiarse de TCO.

Answer 8

Por supuesto, si quiere evitar visitar cada nodo de su árbol cuando cuente, y el tiempo de procesamiento es más valioso para usted que la memoria, puede hacer trampa creando sus cuentas a medida que construye su árbol.

1. Tener un recuento int en cada nodo, inicializado en uno, que represente la cantidad de nodos en el subárbol enraizado en ese nodo.

2. Cuando inserta un nodo, antes de regresar de su rutina de inserción recursiva, incremente el recuento en el nodo actual.

es decir

public void insert(Node root, Node newNode) {
  if (newNode.compareTo(root) > 1) {
    if (root.right != null) 
      insert(root.right, newNode);
    else
      root.right = newNode;
  } else {
    if (root.left != null)
      insert(root.left, newNode);
    else
      root.left = newNode;
  }
  root.count++;
}

Entonces obtener el conteo desde cualquier punto solo implica una búsqueda de node.count

Answer 9

Puedes contar el árbol recorriéndolo de muchas ways . Simplemente preordene el recorrido, el código sería (basado en las funciones que definió):

int count() {
    count = 1;
    if (this.getLeftChild() != null)
        count += this.getLeftChild().count();
    if (this.getRightChild() != null)
        count += this.getRightChild().count();
    return count;
}

Answer 10

Una solución recursiva trivial:

int count() {
   Tree l = getLeftTree();
   Tree r = getRightTree();
   return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}

Un menos trivial no recursivo:

int count() {
    Stack<Tree> s = new Stack<Tree>();
    s.push(this);
    int cnt = 0;
    while (!s.empty()) {
        Tree t = s.pop();
        cnt++;
        Tree ch = getLeftTree();
        if (ch != null) s.push(ch); 
        ch = getRightTree();
        if (ch != null) s.push(ch); 
    }
    return cnt;
}

Este último es probablemente un poco más eficiente en la memoria, porque reemplaza la recursión con una pila y una iteración. También es probablemente más rápido, pero es difícil de decir sin mediciones. Una diferencia clave es que la solución recursiva usa la pila, mientras que la solución no recursiva usa la pila para almacenar los nodos.

Editar: Aquí hay una variante de la solución iterativa, que usa menos la pila:

int count() {
    Tree t = this;
    Stack<Tree> s = new Stack<Tree>();
    int cnt = 0;
    do {
        cnt++;
        Tree l = t.getLeftTree();
        Tree r = t.getRightTree();
        if (l != null) {
            t = l;
            if (r != null) s.push(r);
        } else if (r != null) {
            t = r;
        } else {
            t = s.empty() ? null : s.pop();
        }
    } while (t != null);
    return cnt;
}

Ya sea que necesite una solución más eficiente o más elegante, naturalmente depende del tamaño de sus árboles y de la frecuencia con la que pretenda utilizar esta rutina. Rembemer lo que dijo Hoare: "la optimización prematura es la raíz de todo mal".

Answer 11

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
   return 1 
      + getRightChild() == null? 0 : getRightChild().count()
      + getLeftChild() == null? 0 : getLeftChild().count();
  }
}

Answer 12

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

Tree getLeftChild() {
    // Assume this is already implemented
 }

 int count() {
    if(this.getLeftChild() !=null && this.getRightChild()!=null) 
        return 1 + this.getLeftChild().count() + this.getRightChild().count();
    elseif(this.getLeftChild() !=null && this.getRightChild()==null)
        return 1 + this.getLeftChild().count();
    elseif(this.getLeftChild() ==null && this.getRightChild()!=null)
        return 1 + this.getRightChild().count();
    else return 1;//left & right sub trees are null ==> count the root node
  }
}

Answer 13

int count()

{
   int retval = 1;
    if(null != getRightChild()) retval+=getRightChild().count();
    if(null != getLeftChild()) retval+=getLeftChild().count();
    return retval;

}

Dios, espero no haberme equivocado.

EDITAR: Lo hice en realidad.

Answer 14

int count() {
  Tree right = getRightChild();
  Tree left = getLeftChild();
  int c = 1;                                      // count yourself!
  if ( right != null ) c += right.count();        // count sub trees
  if ( left != null ) c += left.count();          // ..
  return c;
}

Answer 15

return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;

O algo así.