LOS 10 MEJORES ALGORITMOS sobre árboles y  BÚSQUEDA

 

 

1.- Encontrar la profundidad mínima de un árbol binario

2.- Recorrido de suma máxima en un árbol binario

3.- Pre-ordenamiento de la travesía del árbol de búsqueda binaria

4.- Comprobar si un árbol binario es completo o no

5.- Vista inferior de un árbol binario

6.- Nodos de impresión en la vista superior del árbol binario

7.- Eliminar nodos de la raíz a los caminos de las hojas de longitud < K

8.- El ancestro común más bajo en un árbol de búsqueda binario

9.- Comprueba si un árbol binario es subárbol de otro árbol binario

10.- Invertir los niveles alternos de un árbol binario perfecto

 

&&&&&&&&&&

&&&&&&&

&&&

&

 

 

1.- Encontrar la profundidad mínima de un árbol binario

 

Dado un árbol binario, encuentra su mínima profundidad. La profundidad mínima es el número de nodos a lo largo del camino más corto desde el nodo de la raíz hasta el nodo de la hoja más cercano.

 

Por ejemplo, la altura mínima de debajo de un árbol binario es 2.

 

 

Tener en cuenta que el camino debe terminar en un nodo de la hoja

La idea es atravesar el árbol binario dado. Para cada nodo, compruebe si es un nodo de la hoja. Si es así, entonces devuelve 1. Si no es un nodo de hoja, si el subárbol izquierdo es NULL, entonces regrese para el subárbol derecho. Y si el subárbol derecho es NULL, entonces recurre al subárbol izquierdo. Si ambos subárboles, izquierdo y derecho, no son NULL, entonces toma el mínimo de dos alturas.

 

A continuación se muestra la implementación de la idea anterior en lenguaje C++.

 

#include<bits/stdc++.h>

using namespace std;

 

struct Node

{    int data;

    struct Node* left, *right;

};

 

int minDepth(Node *root)

{   if (root == NULL)  return 0;

      // Caso base: Nodo de la hoja, altura = 1.

    if (root->left == NULL && root->right == NULL) return 1;

      // Si el subárbol izquierdo es NULL, recorrer al subárbol derecho

    if (!root->left) return minDepth(root->right) + 1;

      // Si el subárbol derecho es NULL, recorrer al subárbol izquierdo

    if (!root->right)   return minDepth(root->left) + 1;

      return min(minDepth(root->left), minDepth(root->right)) + 1;

}

 

// Creación de Node

Node *newNode(int data)

{   Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return (temp);

}

 

// Programa principal

int main()

{

    // Construimos el Árbol que se muestra en la figura

    Node *root     = newNode(1);

    root->left     = newNode(2);

    root->right     = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    cout <<"The minimum depth of binary tree is : "<< minDepth(root);

    return 0;

}

 

Salida:

La profundidad mínima de este árbol binario es : 2

El tiempo de complejidad de esta solución es O(n)

 

El método anterior puede terminar con una completa travesía del árbol binario incluso cuando la hoja más alta está cerca de la raíz. Una mejor solución es hacer una travesía de orden de nivel. Mientras se hace la travesía, se devuelve la profundidad del primer nodo de la hoja encontrada. A continuación se muestra la implementación de esta solución

 

 #include<bits/stdc++.h>

 using namespace std;

 

 struct Node

 {

 int data;

 struct Node *left, *right;

 };

 

 struct qItem

 { Node *node;

 int depth;

 };

 

 // Método Iterativo

 int minDepth(Node *root)

 {

 if (root == NULL)  return 0;

 queue<qItem> q;

 

 // Inicializa profundidad a 1

 qItem qi = {root, 1};

 q.push(qi);

 

 while (q.empty() == false)

 {

 // Suprime de la cola delantera

 qi = q.front();

 q.pop();

 

 // Detalles de la eliminación

 Node *node = qi.node;

 int depth = qi.depth;

 

 //Si primer nodo visto devuelve su profundidad

 if (node->left == NULL && node->right == NULL)  return depth;

 

 if (node->left != NULL)

{

 qi.node  = node->left;

 qi.depth = depth + 1;

 q.push(qi);

 }

 

 // Si el subárbol derecho no es NULL, añádalo a la la cola

 if (node->right != NULL)

 {

 qi.node  = node->right;

 qi.depth = depth+1;

 q.push(qi);

 }

 }

 return 0;

 }

 

 // Creación de nuevo nodo

 Node* newNode(int data)

 {

 Node *temp = new Node;

 temp->data = data;

 temp->left = temp->right = NULL;

 return temp;

 }

 

 //Programa principal

 int main()

 {

 Node *root = newNode(1);

 root->left = newNode(2);

 root->right = newNode(3);

 root->left->left = newNode(4);

 root->left->right = newNode(5);

 

 cout << minDepth(root);

 return 0;

 }


Salida: 2

 

 

2.- Recorrido de suma máxima en un árbol binario

 

Dando un árbol binario, encuentra la suma máxima del camino. El camino puede comenzar y terminar en cualquier nodo del árbol

Ejemplo:

1

/\

2   3

Salida: 6

 

Descripción: Descripción: Descripción: Descripción: https://media.geeksforgeeks.org/wp-content/cdn-uploads/tree4.png

 

Para cada nodo puede haber cuatro maneras en que el camino máximo pasa por el nodo:

1. Sólo el nodo

2. Camino máximo a través del Hijo Izquierdo + Nodo

3. Camino máximo a través del Hijo derecho + Nodo

4. Camino máximo a través del Hijo Izquierdo + Nodo + Camino máximo a través del Hijo Derecho

 

La idea es mantener el rastro de cuatro caminos y recoger el máximo al final. Una cosa importante a tener en cuenta es que la raíz de cada subárbol necesita devolver la suma máxima del camino de tal manera que como máximo un hijo de la raíz esté involucrado. Esto es necesario para la llamada de la función parental. En el código de abajo, esta suma se almacena en 'max_single' y es devuelta por la función recursiva.

 

#include<bits/stdc++.h>

using namespace std;

  

// Nodo del árbol binario

struct Node

{

    int data;

    struct Node* left, *right;

};

  

struct Node* newNode(int data)

{

    struct Node* newNode = new Node;

    newNode->data = data;

    newNode->left = newNode->right = NULL;

    return (newNode);

}

  

// Esta función devuelve la suma total máxima de la ruta en 'res'.

// Y devuelve la suma máxima del camino que pasa por la raíz.

int findMaxUtil(Node* root, int &res)

{

    if (root == NULL)   return 0;   

  // l y r  almacenan la suma máxima del camino que pasa por la    //izquierda y el hijo derecho de la raíz respectivamente    

int l = findMaxUtil(root->left,res);

    int r = findMaxUtil(root->right,res);

  

// Ruta máxima para la llamada de la raíz. Este camino debe

    // incluyen como máximo un hijo de la raíz

 int max_single = max(max(l, r) + root->data, root->data);

  

    // Max Top representa la suma cuando el Nodo bajo

    // la consideración es la raíz del camino del máximo y no

    // los ancestros de la raíz están ahí en el camino de la suma //máxima

    int max_top = max(max_single, l + r + root->data);  

    res = max(res, max_top);  

    return max_single;

}

  

// Devuelve la suma máxima del camino en el árbol con la raíz dada

int findMaxSum(Node *root)

{

    // Inicializa

    int res = INT_MIN;

  

    // Calcula y devuelve el resultado

    findMaxUtil(root, res);

    return res;

}

  

// Programa conductor principal

int main(void)

{

    struct Node *root = newNode(10);

    root->left        = newNode(2);

    root->right       = newNode(10);

    root->left->left  = newNode(20);

    root->left->right = newNode(1);

    root->right->right = newNode(-25);

    root->right->right->left   = newNode(3);

    root->right->right->right  = newNode(4);

    cout << "Max path sum is " << findMaxSum(root);

    return 0;

}


Salida: La suma máxima es 42

Complejidad: O(n)

 

 

3.- Comprueba si un arreglo dado puede representar el pre-ordenamiento de la travesía del árbol de búsqueda binaria

 

Dada una serie de números, el retorno es verdadero si la serie dada puede representar el pre-ordenamiento de un árbol de búsqueda binaria, si no, el retorno es falso. La complejidad temporal esperada es O(n).

 

Ejemplos:

Entrada: pre={2,4,3]    Salida: verdadero

Un arreglo dado puede representar un pre-ordenamiento transversal

de debajo del árbol

 

Entrada: pre={2,4,1]    Salida: falso

 

Entrada: pre={40,30,35,80,100]    Salida: verdadero

 

Una solución sencilla es hacer el seguimiento de cada nodo pre[i] empezando por el primero.

 

1) Encontrar el primer valor mayor en el lado derecho del nodo actual.

   Deja que el índice de este nodo sea j. Devuelve true si lo siguiente

   las condiciones se mantienen. Si no, la devolución es falsa.

    (i) Todos los valores después del valor mayor encontrado arriba son

         mayor que el nodo actual.

    ii) Llamadas recursivas para los submatrices pre[i+1..j-1] y

         pre[j+1..n-1] también vuelven a ser verdaderos.

La complejidad temporal de la solución anterior es O(n2)

 

Una Solución Eficiente puede resolver este problema en O(n) tiempo. La idea es usar una pila. Este problema es similar al problema del siguiente (o más cercano) elemento mayor. Aquí encontramos el siguiente elemento mayor y después de encontrar el siguiente mayor, si encontramos un elemento más pequeño, entonces devuelve falso

 

1) Crear una pila vacía.

2) Inicializar la raíz como INT_MIN.

3) Haz lo siguiente para cada elemento pre[i]

     a) Si pre[i] es más pequeño que la raíz actual, devuelva falso.

     b) Siga quitando elementos de la pila mientras pre[i] sea mayor

        y luego apilarlos. Hacer que el último elemento eliminado sea una nueva raíz (para

        se comparará a continuación).

        En este punto, el pre[i] es mayor que la raíz eliminada

        (Por eso si vemos un elemento más pequeño en el paso a), nosotros

        retorno falso)

     c) empujar pre[i] a la pila (Todos los elementos en la pila están en disminución

        orden) 

A continuación se muestra la aplicación de la idea anterior en lenguaje C++:

 

#include<bits/stdc++.h>

using namespace std;

  

bool canRepresentBST(int pre[], int n)

{

    stack<int> s;

  

    //Inicia valor

    int root = INT_MIN;

  

   for (int i=0; i<n; i++)

    {

       if (pre[i] < root)   return false;

  

        // Si está en el subárbol derecho de la parte superior de //la pila,

        // Sigue quitando los artículos más pequeños que pre[i]

        // y hacer que el último elemento eliminado sea nuevo

        // raíz.

        while (!s.empty() && s.top()<pre[i])

        {   root = s.top();

            s.pop();

        }

  

        // En este punto, o bien la pila está vacía o

        // es más pequeño que la raíz, empuja la raíz

        s.push(pre[i]);

    }

    return true;

}

  

// Programa principal

int main()

{

    int pre1[] = {40, 30, 35, 80, 100};

    int n = sizeof(pre1)/sizeof(pre1[0]);

    canRepresentBST(pre1, n)? cout << "verdadero":

                              cout << "falso";

  

    int pre2[] = {40, 30, 35, 20, 80, 100};

    n = sizeof(pre2)/sizeof(pre2[0]);

    canRepresentBST(pre2, n)? cout << "verdadero":

                              cout << "falso";

  

    return 0;

}


Salida:  verdadero    falso

 

 

4.- Comprobar si un árbol binario es completo o no

 

Un árbol binario completo se define como un árbol binario en el que todos los nodos tienen cero o dos nodos hijos. Por el contrario, no hay ningún nodo en un árbol binario completo, que tiene un nodo hijo.

Por ejemplo:

 

Para comprobar si un árbol binario es un árbol binario completo necesitamos probar los siguientes casos:-

 

1) Si un nodo del árbol binario es NULL, entonces es un árbol binario completo.

2) Si un nodo de árbol binario tiene subárboles izquierdo y derecho vacíos, entonces es un árbol binario completo por definición.

3) Si un nodo de árbol binario tiene subárboles izquierdo y derecho, entonces es una parte de un árbol binario completo por definición. En este caso, compruebe de forma recursiva si los subárboles izquierdo y derecho son también árboles binarios en sí mismos.

4) En todas las demás combinaciones de subárboles de derecha e izquierda, el árbol binario no es un árbol binario completo.

 

A continuación se muestra la implementación para comprobar si un árbol binario es un árbol binario completo, en lenguaje C++.

 

#include <bits/stdc++.h>   

using namespace std;

   

struct Node

{

    int key;

    struct Node *left, *right;

};

   

struct Node *newNode(char k)

{

    struct Node *node = new  Node;

    node->key = k;

    node->right = node->left = NULL;

    return node;

}

   

bool isFullTree (struct Node* root)

{

        if (root == NULL)     return true;

   

        if (root->left == NULL && root->right == NULL)     return true;

   

       if ((root->left) && (root->right))         return (isFullTree(root->left) && isFullTree(root->right));

   

    return false;

}

   

// Programa principal

int main()

{

    struct Node* root = NULL;

    root = newNode(10);

    root->left = newNode(20);

    root->right = newNode(30);

   

    root->left->right = newNode(40);

    root->left->left = newNode(50);

    root->right->left = newNode(60);

    root->right->right = newNode(70);

   

    root->left->left->left = newNode(80);

    root->left->left->right = newNode(90);

    root->left->right->left = newNode(80);

    root->left->right->right = newNode(90);

    root->right->left->left = newNode(80);

    root->right->left->right = newNode(90);

    root->right->right->left = newNode(80);

    root->right->right->right = newNode(90);

   

    if (isFullTree(root))     cout << "El árbol binario es completo";

    else    cout << " El árbol binario no es completo ";

   

    return(0);

}

Salida: El árbol binario es completo

La complejidad temporal del código anterior es O(n), donde n es el número de nodos en un árbol binario dado.

 

 

5.- Vista inferior de un árbol binario

 

Dado un árbol binario, necesitamos imprimir la vista inferior de izquierda a derecha. Un nodo x está ahí en la salida si x es el nodo más bajo en su distancia horizontal. La distancia horizontal del hijo izquierdo del nodo x es igual a la distancia horizontal de x menos 1, y la del hijo derecho es la distancia horizontal de x más 1.

Ejemplo:

  20

   /    \

      8       22

 /   \      \

    5      3      25

  / \     

    10    14

 

Para el árbol anterior el resultado debe ser 5, 10, 3, 14, 25.

 

Si hay varios nodos inferiores para una distancia horizontal de la raíz, entonces imprima el último en el nivel transversal. Por ejemplo, en el siguiente diagrama, 3 y 4 son los dos nodos más bajos a la distancia horizontal 0, necesitamos imprimir 4.

                   20

                    /    \

                  8       22

                /   \    /   \

              5      3 4     25

                    / \     

                  10    14

Para el árbol anterior el resultado debe ser  5, 10, 4, 14, 25.

 

Método: Usando la cola

 

Los siguientes son los pasos para imprimir la vista inferior del árbol binario.

1. Ponemos los nodos del árbol en una cola para la travesía del orden de los niveles.

2. 2. Empezamos con la distancia horizontal(hd) 0 del nodo raíz, seguimos añadiendo el hijo izquierdo a la cola junto con la distancia horizontal como hd-1 y el hijo derecho como hd+1.

3. Además, usa un TreeMap que almacena el par de valores de las claves ordenados por clave.

4. Cada vez que nos encontremos con una nueva distancia horizontal o una distancia horizontal existente, ponemos los datos del nodo para la distancia horizontal como clave. Por primera vez se añadirá al mapa, la próxima vez reemplazará el valor. Esto asegurará que el elemento más inferior para esa distancia horizontal esté presente en el mapa y si ves el árbol de abajo verás ese elemento.

 

#include<bits/stdc++.h>

using namespace std;

  

struct Node

{

    int data;

    int hd;

    Node *left, *right;  

    

    Node(int key)

    {

        data = key;

        hd = INT_MAX;

        left = right = NULL;

    }

};

  

void bottomView(Node *root)

{

    if (root == NULL)   return;   

   int hd = 0;   

  map<int, int> m;

     

 queue<Node *> q;

  

 root->hd = hd;

 q.push(root); 

  

 while (!q.empty())

    {

        Node *temp = q.front();

        q.pop();    

        hd = temp->hd;

        m[hd] = temp->data;

  

        if (temp->left != NULL)

        {

            temp->left->hd = hd-1;

            q.push(temp->left);

        }

  

       if (temp->right != NULL)

        {

            temp->right->hd = hd+1;

            q.push(temp->right);

        }

    }

  

  for (auto i = m.begin(); i != m.end(); ++i)

        cout << i->second << " ";

}

  

// Programa principal

int main()

{

    Node *root = new Node(20);

    root->left = new Node(8);

    root->right = new Node(22);

    root->left->left = new Node(5);

    root->left->right = new Node(3);

    root->right->left = new Node(4);

    root->right->right = new Node(25);

    root->left->right->left = new Node(10);

    root->left->right->right = new Node(14);

    cout << "Bottom view of the given binary tree :\n"

    bottomView(root);

    return 0;

}

Salida: 5,10,4,14,25

 

6.- Nodos de impresión en la vista superior del árbol binario

 

La vista superior de un árbol binario es el conjunto de nodos visibles cuando el árbol se ve desde la cima. Dado un árbol binario, imprime la vista superior del mismo. Los nodos de salida se pueden imprimir en cualquier orden.

 

Un nodo x está ahí en la salida si x es el nodo más alto en su distancia horizontal. La distancia horizontal del hijo izquierdo del nodo x es igual a la distancia horizontal de x menos 1, y la del hijo derecho es la distancia horizontal de x más 1.

 

     1

    /     \

   2       3

  /  \    / \

 4    5  6   7

La vista superior del árbol binario anterior es    4 2 1 3 7

 

        1

      /   \

    2       3

      \  

        4 

          \

            5

             \

               6

La vista superior del árbol binario anterior es  2 1 3 6

 

La idea es hacer algo similar al Orden Traversal vertical. Al igual que en el Orden Traversal vertical, necesitamos poner juntos nodos de la misma distancia horizontal. Hacemos una travesía de orden nivelada de modo que el nodo superior de un nodo horizontal sea visitado antes que cualquier otro nodo de la misma distancia horizontal que esté debajo de él. Hashing se utiliza para comprobar si un nodo a una determinada distancia horizontal se ve o no.

 

#include <bits/stdc++.h>

using namespace std;

  

struct Node

{

    Node * left;

    Node* right;

    int hd;

    int data;

};

  

Node* newNode(int key)

{

    Node* node=new Node();

    node->left = node->right = NULL;

    node->data=key;

    return node;

}

  

void topview(Node* root)

{

    if(root==NULL)

       return;

     queue<Node*>q;

     map<int,int> m; 

     int hd=0;

     root->hd=hd;

       

    q.push(root);

      

    cout<< "The top view of the tree is : \n";

      

    while(q.size())

    {

        hd=root->hd;

          

        if(m.count(hd)==0)  

        m[hd]=root->data;

        if(root->left)

        {

            root->left->hd=hd-1;

            q.push(root->left);

        }

        if(root->right)

        {

            root->right->hd=hd+1;

            q.push(root->right);

        }

        q.pop();

        root=q.front();

        

    }

          

     for(auto i=m.begin();i!=m.end();i++)

    {

        cout<<i->second<<" ";

    }

      

}

   

// Programa principal

int main()

{

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->right = newNode(4);

    root->left->right->right = newNode(5);

    root->left->right->right->right = newNode(6);

    cout<<"Following are nodes in top view of Binary Tree\n"; 

    topview(root);

    return 0;

}


Output:    A continuación se muestran los nodos en la vista superior del Árbol Binario    2136

 

La complejidad temporal de la implementación anterior es O(nlogn) donde n es el número de nodos en el árbol binario dado con cada operación de inserción en el mapa que requiere complejidad O(log2n).

 

 

7.- Eliminar nodos de la raíz a los caminos de las hojas de longitud < K

 

Dado un Árbol Binario y un número k, se eliminan todos los nodos que se encuentran sólo en caminos de raíz a hoja de longitud inferior a k. Si un nodo X se encuentra en múltiples caminos de raíz a hoja y si alguno de los caminos tiene una longitud de camino >= k, entonces X no se elimina del Árbol Binario. En otras palabras, un nodo se elimina si todos los caminos que lo atraviesan tienen longitudes menores que k.

 

Consideremos el siguiente ejemplo de Árbol Binario

              1

           /      \

         2          3

      /     \         \

    4         5        6

  /                   /

 7                   8

Entrada: Raíz del árbol binario anterior   k = 4

 

Salida: El árbol debe cambiarse a 

           1

        /     \

      2          3

     /             \

   4                 6

 /                  /

7                  8

Tres pasos

i) 1->2->4->7      --  4

ii) 1->2->5         -- 3

iii) 1->3->6->8   -- 4

 

Recomendamos encarecidamente que minimice su navegador y lo pruebe usted mismo primero

 

La idea aquí es usar el travesía del árbol por correo. Antes de eliminar un nodo, debemos comprobar que todos los hijos de ese nodo en el camino más corto ya han sido eliminados.

 

Hay dos casos:

i) Este nodo se convierte en un nodo de la hoja, en cuyo caso debe ser eliminado.

ii) Este nodo tiene otro hijo en un camino con una longitud de camino >= k. En ese caso no necesita ser eliminado.

 

La implementación del enfoque anterior es la siguiente:

 

#include<bits/stdc++.h>

usando namespace std;

 

struct Nodo

{

    datos de inteligencia;

    Nodo *izquierda, *derecha;

};

 

//Nuevo nodo de un árbol

Nodo *nuevoNodo(int datos)

{

    Nodo *nodo = nuevo nodo;

    nodo->datos = datos;

    nódulo->izquierda = nódulo->derecha = NULL;

    nodo de retorno;

}

 

// Método de utilidad que realmente elimina los nodos que no son

// en el pathLen >= k. Este método puede cambiar la raíz también.

Nodo *removeShortPathNodesUtil(Nodo *root, nivel int, int k)

{

    //Condición de base

    si (raíz == NULL)

        Regresa NULL;

 

    // Atravesar el árbol en forma de postorden para que si una hoja

    // la longitud de la ruta del nodo es más corta que k, entonces ese nodo y

    // todos sus descendientes hasta el nodo que no son

    // en algún otro camino se eliminan.

    root->left = removeShortPathNodesUtil(root->left, level + 1, k);

    root->right = removeShortPathNodesUtil(root->right, level + 1, k);

 

    // Si la raíz es un nodo de la hoja y su nivel es menor que k entonces

    // quitar este nodo.

    // Esto sube y comprueba los nodos de los ancestros también para el

    // la misma condición hasta que encuentre un nodo que sea parte de otro

    // camino(s) también.

    si (raíz->izquierda == NULL && raíz->derecha == NULL && nivel < k)

    {

        borrar la raíz;

        devolver NULL;

    }

 

    // Volver a la raíz;

    ...volver a la raíz;

}

 

// Método que llama el método de la utitlidad para eliminar el camino corto

// Nodos.

Nodo *removeShortPathNodes(Nodo *root, int k)

{

    int pathLen = 0;

    return removeShortPathNodesUtil(root, 1, k);

}

 

//Método para imprimir el árbol de manera ordenada.

anular printInorder(Nodo *Raíz)

{

    si (raíz)

    {

        printInorder(root->left);

        cout << raíz->datos << " ";

        printInorder(root->right);

    }

}

 

// Programa principal

int main()

{

    int k = 4;

    Nodo *raíz = nuevoNodo(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->left->left->left = newNode(7);

    root->right->right = newNode(6);

    root->derecha->derecha->izquierda = newNode(8);

    cout << "Inorder Traversal of Original tree" << endl;

    printInorder(root);

    cout << endl;

    cout << "Inorder Traversal of Modified tree" << endl;

    Nodo *res = removeShortPathNodes(root, k);

    printInorder(res);

    return 0;

}

 

Salida:  Travesía en orden del árbol original    7 4 2 5 1 3 8 6

Travesía en orden del árbol modificado           7 4 2 1 3 8 6

 

La complejidad temporal de la solución anterior es O(n), donde n es el número de nodos en un determinado Árbol Binario.

 

 

8.- El ancestro común más bajo en un árbol de búsqueda binario

 

Dados los valores de dos valores n1 y n2 en un Árbol de Búsqueda Binario, encontrar el Ancestro Común más bajo (LCA). Puedes asumir que ambos valores existen en el árbol.

 

Para el árbol de búsqueda binaria, mientras se recorre el árbol de arriba a abajo el primer nodo que se encuentra entre los dos números n1 y n2 es el ACV de los nodos, es decir, el primer nodo n con la menor profundidad que se encuentra entre n1 y n2 (n1<=n<=n2) n1 < n2. Así que atraviesa la BST de forma recursiva, si el valor del nodo es mayor que n1 y n2 entonces nuestro LCA se encuentra en el lado izquierdo del nodo, si es menor que n1 y n2, entonces el LCA se encuentra en el lado derecho. De lo contrario, la raíz es LCA (asumiendo que tanto n1 como n2 están presentes en la BST).

 

Algoritmo:

Crea una función recursiva que toma un nodo y los dos valores n1 y n2.

Si el valor del nodo actual es menor que tanto n1 como n2, entonces LCA se encuentra en el subárbol derecho. Llama a la función recursiva del subárbol derecho.

Si el valor del nodo actual es mayor que los dos valores n1 y n2, entonces LCA se encuentra en el subárbol izquierdo. Llame a la función recursiva para el subárbol izquierdo.

Si los dos casos anteriores son falsos, entonces devuelva el nodo actual como LCA.

 

#include <bits/stdc++.h>

using namespace std;

  

class node 

    public:

    int data; 

    node* left, *right; 

}; 

  

node *lca(node* root, int n1, int n2) 

    if (root == NULL) return NULL; 

  

   if (root->data > n1 && root->data > n2)  return lca(root->left, n1, n2); 

   if (root->data < n1 && root->data < n2)  return lca(root->right, n1, n2); 

  

    return root; 

  

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = Node->right = NULL; 

    return(Node); 

  

//Programa principal

int main() 

    node *root = newNode(20); 

    root->left = newNode(8); 

    root->right = newNode(22); 

    root->left->left = newNode(4); 

    root->left->right = newNode(12); 

    root->left->right->left = newNode(10); 

    root->left->right->right = newNode(14); 

  

    int n1 = 10, n2 = 14; 

    node *t = lca(root, n1, n2); 

    cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl; 

  

    n1 = 14, n2 = 8; 

    t = lca(root, n1, n2); 

    cout<<"LCA of " << n1 << " and " << n2 << " is " << t->data << endl; 

  

    n1 = 10, n2 = 22; 

    t = lca(root, n1, n2); 

    cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; 

    return 0; 

 

 

Análisis de la complejidad:

 

Complejidad del tiempo: O(h).

La complejidad temporal de la solución anterior es O(h), donde h es la altura del árbol.

Complejidad del espacio: O(1).

Si se ignora el espacio recursivo de la pila, la complejidad espacial de la solución anterior es constante.

 

 

9.- Comprueba si un árbol binario es subárbol de otro árbol binario

 

Dados dos árboles binarios, comprueba si el primer árbol es subárbol del segundo. Un subárbol de un árbol T es un árbol S que consiste en un nodo en T y todos sus descendientes en T.

El subárbol correspondiente al nodo raíz es el árbol entero; el subárbol correspondiente a cualquier otro nodo se denomina subárbol propiamente dicho.

 

Por ejemplo:

    Árbol  1

          x

        /    \

      a       b

       \

        c

 

 

        Árbol  2

              z

            /   \

          x      e

        /    \     \

      a       b      k

       \

        c

 

Hemos discutido una solución de O(n2) para este problema. En este post se discute una solución de O(n). La idea se basa en el hecho de que el inorden y el preorden/postorden identifican de manera única un árbol binario. El árbol S es un subárbol de T si tanto las travesías inorder y preorder de S son subcadenas de las travesías inorden y preorden de T respectivamente.

 

A continuación se detallan los pasos a seguir.

 

1) Encontrar las travesías en orden y en preorden de T, almacenarlas en dos arreglos auxiliares enT[] y preT[].

 

2) Encontrar las travesías en orden y en preorden de S, almacenarlas en dos arreglos auxiliares enS[] y preS[].

 

3) Si inS[] es una submatriz de inT[] y preS[] es una submatriz preT[], entonces S es un subárbol de T. De lo contrario, no.

 

También podemos utilizar el postorder transversal en lugar del preordenamiento en el algoritmo anterior.

 

Consideremos el ejemplo anterior

 

Las travesías Inorden y Preorden del gran árbol son.

inT[] = {a, c, x, b, z, e, k}

preT[] = {z, x, a, c, b, e, k}

 

Las travesías Inorden y Preorden del árbol pequeño son

inS[] = {a, c, x, b}

preS[] = {x, a, c, b}

 

Podemos descubrir fácilmente que inS[] es un subconjunto de

inT[] y preS[] es un subconjunto de preT[].

 

El algoritmo anterior puede extenderse para manejar tales casos añadiendo un carácter especial siempre que nos encontremos con NULL en las travesías de inorden y preorden.

 

En lenguaje C++:

#include <cstring>

#include <iostream>

using namespace std;

#define MAX 100

  

struct Node {

    char key;

    struct Node *left, *right;

};

  

Node* newNode(char item)

{

    Node* temp = new Node;

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

  

void storeInorder(Node* root, char arr[], int& i)

{

    if (root == NULL) {

        arr[i++] = '$';

        return;

    }

    storeInorder(root->left, arr, i);

    arr[i++] = root->key;

    storeInorder(root->right, arr, i);

}

  

void storePreOrder(Node* root, char arr[], int& i)

{

    if (root == NULL) {

        arr[i++] = '$';

        return;

    }

    arr[i++] = root->key;

    storePreOrder(root->left, arr, i);

    storePreOrder(root->right, arr, i);

}

  

bool isSubtree(Node* T, Node* S)

{

    if (S == NULL)

        return true;

    if (T == NULL)

        return false;

  

    int m = 0, n = 0;

    char inT[MAX], inS[MAX];

    storeInorder(T, inT, m);

    storeInorder(S, inS, n);

    inT[m] = '\0', inS[n] = '\0';

  

    if (strstr(inT, inS) == NULL)     return false;

  

    m = 0, n = 0;

    char preT[MAX], preS[MAX];

    storePreOrder(T, preT, m);

    storePreOrder(S, preS, n);

    preT[m] = '\0', preS[n] = '\0';

  

    return (strstr(preT, preS) != NULL);

}

  

// Programa principal

int main()

{

    Node* T = newNode('a');

    T->left = newNode('b');

    T->right = newNode('d');

    T->left->left = newNode('c');

    T->right->right = newNode('e');

  

    Node* S = newNode('a');

    S->left = newNode('b');

    S->left->left = newNode('c');

    S->right = newNode('d');

  

    if (isSubtree(T, S))

        cout << "Yes: S is a subtree of T";

    else

        cout << "No: S is NOT a subtree of T";

  

    return 0;

}

Salida: No: S no es un subárbol de T

 

Complejidad temporal: Las travesías en orden y en preorden del Árbol Binario toman O(n) tiempo. La función strstr() también puede implementarse en O(n) tiempo usando el algoritmo de concordancia de cadenas KMP.

 

Espacio auxiliar: O(n)

 

10.- Invertir los niveles alternos de un árbol binario perfecto

 

Si se le da un Árbol Binario Perfecto, se invierten los nodos de nivel alterno del árbol binario.

 

Árbol dado:

               a

            /     \

           b       c

         /  \     /  \

        d    e    f    g

       / \  / \  / \  / \

       h  i j  k l  m  n  o

 

Árbol modificado:

             a

            /     \

           c       b

         /  \     /  \

        d    e    f    g

       / \  / \  / \  / \

      o  n m  l k  j  i  h

 

Una solución sencilla es hacer los siguientes pasos:

 

1) Acceder a los nodos nivel por nivel.

2) Si el nivel actual es impar, entonces almacena los nodos de este nivel en un arreglo.

3) Invertir la matriz y almacenar los elementos de nuevo en el árbol.

 

 

Otra solución es hacer dos travesías en orden. Los siguientes son los pasos a seguir:

 

1) Atravesar el árbol dado en orden y almacenar todos los nodos de nivel impar en un arreglo auxiliar. Para el árbol dado de ejemplo anterior, el contenido de la matriz se convierte en {h, i, b, j, k, l, m, c, n, o}

 

2) Invierta la matriz. La matriz ahora se convierte en {o, n, c, m, l, k, j, b, i, h}

 

3) Atravesar el árbol de nuevo en forma ordenada. Mientras atraviesan el árbol, uno por uno toman elementos de la matriz y almacenan elementos de la matriz a cada nodo atravesado en algún nivel.

Para el ejemplo anterior, atravesamos la "h" primero en la matriz y reemplazamos la "h" por la "o". Luego atravesamos la "i" y la reemplazamos con la "n".

 

En lenguaje C++:

 

#include<bits/stdc++.h>

#define MAX 100

using namespace std;

  

struct Node

{

    char data;

    struct Node *left, *right;

};

  

struct Node *newNode(char item)

{

    struct Node *temp =  new Node;

    temp->data = item;

    temp->left = temp->right = NULL;

    return temp;

}

  

 

void storeAlternate(Node *root, char arr[], int *index, int l)

{

    // Base case

    if (root == NULL) return;

  

    storeAlternate(root->left, arr, index, l+1);

  

   if (l%2 != 0)

    {

        arr[*index] = root->data;

        (*index)++;

    }

  

   storeAlternate(root->right, arr, index, l+1);

}

  

 

void modifyTree(Node *root, char arr[], int *index, int l)

{

       if (root == NULL) return;   

       modifyTree(root->left, arr, index, l+1);   

       if (l%2 != 0)

    {

        root->data = arr[*index];

        (*index)++;

    }

  

    modifyTree(root->right, arr, index, l+1);

}

  

void reverse(char arr[], int n)

{

    int l = 0, r = n-1;

    while (l < r)

    {

        int temp = arr[l];

        arr[l] = arr[r];

        arr[r] = temp;

        l++; r--;

    }

}

  

void reverseAlternate(struct Node *root)

{

    char *arr = new char[MAX];

    int index = 0;

  

    storeAlternate(root, arr, &index, 0);   

   reverse(arr, index);    

    index = 0;

    modifyTree(root, arr, &index, 0);

}

  

void printInorder(struct Node *root)

{

    if (root == NULL) return;

    printInorder(root->left);

    cout << root->data << " ";

    printInorder(root->right);

}

  

// Programa principal

int main()

{

    struct Node *root = newNode('a');

    root->left = newNode('b');

    root->right = newNode('c');

    root->left->left = newNode('d');

    root->left->right = newNode('e');

    root->right->left = newNode('f');

    root->right->right = newNode('g');

    root->left->left->left = newNode('h');

    root->left->left->right = newNode('i');

    root->left->right->left = newNode('j');

    root->left->right->right = newNode('k');

    root->right->left->left = newNode('l');

    root->right->left->right = newNode('m');

    root->right->right->left = newNode('n');

    root->right->right->right = newNode('o');

  

    cout << "Inorder Traversal of given tree\n";

    printInorder(root);   

    reverseAlternate(root);   

    cout << "\n\nInorder Traversal of modified tree\n";

    printInorder(root);

  

    return 0;

}

Salida: Travesía del árbol determinado

h d i b j e k a l f m c n g o

 

Travesía del árbol modificado

o d n c m e l a k f j b i g h

 

La complejidad temporal de la solución anterior es O(n) como lo hace dos travesías en orden de árbol binario.

 

 

&&&&&&&&&&&&&

&&&&&&&&&

&&&&&

&