c++ - imprimir - como hacer un arbol binario

Búsqueda de nodos en la pila de desbordamientos de árboles binarios

Question

Utilizo el siguiente método para atravesar * un árbol binario de 300 000 niveles:

Node* find(int v){
   if(value==v)
      return this;
   else if(right && value<v)
      return right->find(v); 
   else if(left && value>v)
      return left->find(v);
}

Sin embargo, me sale una falla de segmentación debido al desbordamiento de pila. ¿Alguna idea sobre cómo atravesar el árbol profundo sin la sobrecarga de llamadas a funciones recursivas?

* Por "transversal" me refiero a "buscar un nodo con un valor dado", no a través de un árbol completo.

Answer 1

Bueno, se puede hacer cola recursiva al costo de una sola variable local adicional y algunas comparaciones:

Node* find(int v){
  if(value==v)
    return this;
  else if(!right && value<v)
    return NULL;
  else if(!left && value>v)
    return NULL;
  else {
    Node *tmp = NULL;
    if(value<v)
      tmp = right;
    else if(value>v)
      tmp = left;
    return tmp->find(v);
  }
}

Answer 2

Caminar a través de un árbol binario es un proceso recursivo, en el que continuará caminando hasta que encuentre que el nodo en el que se encuentra actualmente no apunta a ninguna parte.

Es que necesitas una condición base adecuada. Algo que se parece a:

if (treeNode == NULL)
   return NULL;

En general, atravesar un árbol se logra de esta manera (en C):

void traverse(treeNode *pTree){
  if (pTree==0)
    return;
  printf("%d/n",pTree->nodeData);
  traverse(pTree->leftChild);
  traverse(pTree->rightChild);
}

Answer 3

Cuando el árbol que tiene es un Árbol de búsqueda binario , y todo lo que quiere hacer es buscar un nodo que tenga un valor específico, entonces las cosas son simples: no es necesaria la recursión, puede hacerlo usando un bucle simple como otros han señalado.

En el caso más general de tener un árbol que no es necesariamente un árbol de búsqueda binario, y querer realizar un recorrido completo de la misma, la forma más simple es usar la recursión, pero como ya entiende, si el árbol es muy profundo, entonces la recursión no trabajará.

Por lo tanto, para evitar la recursión, debe implementar una pila en el montón de C ++. StackElement declarar una nueva clase StackElement que contendrá un miembro por cada variable local que tenía su función recursiva original, y un miembro por cada parámetro que su función recursiva original aceptó. (Es posible que pueda salirse con menos variables de miembro, puede preocuparse por eso después de haber conseguido que su código funcione).

Puede almacenar instancias de StackElement en una colección de pila, o simplemente puede hacer que cada una de ellas contenga un puntero a su padre, implementando la pila completamente por sí mismo.

Entonces, en lugar de que su función se llame a sí misma de forma recursiva, simplemente consistirá en un bucle. Su función ingresa en el bucle con el StackElement actual siendo inicializado con información sobre el nodo raíz de su árbol. Su puntero principal será nulo, que es otra forma de decir que la pila estará vacía.

En cada lugar donde la versión recursiva de su función se llamaba a sí misma, su nueva función asignará una nueva instancia de StackElement , la inicializará y repetirá el bucle utilizando esta nueva instancia como el elemento actual .

En cada lugar donde la versión recursiva de su función estaba regresando, su nueva función liberará el StackElement actual , haciendo estallar el que estaba sentado en la parte superior de la pila, convirtiéndolo en el nuevo elemento actual y repitiendo el bucle.

Cuando encuentra el nodo que estaba buscando, simplemente rompe con el bucle.

Alternativamente, si el nodo de su árbol existente admite a) un enlace a su nodo "padre" yb) datos de usuario (donde puede almacenar una bandera "visitada"), entonces no necesita implementar su propia pila, puede solo atraviese el árbol en el lugar: en cada iteración de su bucle, primero verifique si el nodo actual es el nodo que estaba buscando; si no, entonces enumera a través de los niños hasta que encuentre uno que no ha sido visitado todavía, y luego lo visita; cuando llega a una hoja, o un nodo cuyos hijos han sido visitados, luego retrocede siguiendo el enlace al padre. Además, si tiene la libertad de destruir el árbol mientras lo atraviesa, entonces ni siquiera necesita el concepto de "datos de usuario": una vez que haya terminado con un nodo secundario, lo libera y lo nula.

Answer 4

Puede implementar la recursión no utilizando la pila de llamadas sino una pila definida por el usuario o algo similar; Esto podría hacerse a través de la plantilla de stack existente. El enfoque sería tener un bucle while que itere hasta que la pila esté vacía; Como la implementación existente utiliza la búsqueda en profundidad, la eliminación de las llamadas recursivas se puede encontrar here .

Answer 5

Un bucle simple en el que tiene una variable de tipo Nodo * que establece en el siguiente nodo, luego haga un bucle nuevamente ...
¡No olvide el caso de que el valor que está buscando no existe!

Answer 6

¡Sí! Para un árbol de 300 000 niveles evitar la recursión . Recorra su árbol y encuentre el valor de forma iterativa utilizando un bucle.

Representación binaria de búsqueda

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

Sólo para aclarar el problema aún más. Tu árbol tiene una profundidad de n = 300.000 niveles . Por lo tanto, en el peor de los casos, un árbol de búsqueda binaria (BST) tendrá que visitar TODOS los nodos del árbol. Esta es una mala noticia porque el caso más desfavorable tiene una complejidad de tiempo O (n) algorítmica. Tal árbol puede tener:

2ˆ300.000 nodos = 9.9701e + 90308 nodos (aproximadamente).

9.9701e + 90308 nodos es un número exponencialmente masivo de nodos para visitar. Con estos números queda tan claro por qué la pila de llamadas se desborda.

Solución (forma iterativa):

Supongo que la declaración de class / struct Nodo es un entero estándar BST uno clásico. Entonces podrías adaptarlo y funcionará:

struct Node {
    int data;
    Node* right;
    Node* left;
};

Node* find(int v) {
    Node* temp = root;  // temp Node* value copy to not mess up tree structure by changing the root
    while (temp != nullptr) {
        if (temp->data == v) {
            return temp;
        }
        if (v > temp->data) {
            temp = temp->right;
        }
        else {
            temp = temp->left;
        }
    }
    return nullptr;
}

Tomar este enfoque iterativo evita la recursión , por lo que le ahorra la molestia de tener que encontrar recursivamente el valor en un árbol tan grande con la pila de llamadas de su programa.