LOS
10 MEJORES ALGORITMOS sobre árboles y
BÚSQUEDA
&&&&&&&&&&
&&&&&&&
&&&
&
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
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)
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.
&&&&&&&&&&&&&
&&&&&&&&&
&&&&&
&