algorithm
Arboles
Buscar..
Observaciones
Los árboles son una subcategoría o subtipo de gráficos de borde de nodo. Son omnipresentes dentro de la informática debido a su prevalencia como modelo para muchas estructuras algorítmicas diferentes que, a su vez, se aplican en muchos algoritmos diferentes.
Introducción
Los árboles son un subtipo de la estructura de datos más general del gráfico de borde de nodo.
Para ser un árbol, una gráfica debe satisfacer dos requisitos:
- Es acíclico. No contiene ciclos (o "bucles").
- Esta conectado. Para cualquier nodo dado en el gráfico, cada nodo es accesible. Todos los nodos son accesibles a través de una ruta en el gráfico.
La estructura de datos del árbol es bastante común dentro de la informática. Los árboles se utilizan para modelar muchas estructuras de datos algorítmicos diferentes, como árboles binarios ordinarios, árboles rojo-negros, árboles B, árboles AB, árboles 23, Heap, y tries.
es común referirse a un árbol como un Rooted Tree por:
choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)
símbolo común para los árboles: T
Representación típica del árbol del árbol.
Normalmente, representamos un árbol de anarios (uno con hijos potencialmente ilimitados por nodo) como un árbol binario (uno de ellos con exactamente dos hijos por nodo). El "siguiente" niño es considerado como un hermano. Tenga en cuenta que si un árbol es binario, esta representación crea nodos adicionales.
Luego iteramos sobre los hermanos y asistimos a los niños. Como la mayoría de los árboles son relativamente poco profundos: muchos niños, pero solo unos pocos niveles de jerarquía, dan lugar a un código eficiente. Tenga en cuenta que las genealogías humanas son una excepción (muchos niveles de ancestros, solo unos pocos niños por nivel).
Si es necesario, se pueden guardar punteros hacia atrás para permitir que el árbol ascienda. Estos son más difíciles de mantener.
Tenga en cuenta que es típico tener una función para llamar a la raíz y una función recursiva con parámetros adicionales, en este caso, la profundidad del árbol.
struct node
{
struct node *next;
struct node *child;
std::string data;
}
void printtree_r(struct node *node, int depth)
{
int i;
while(node)
{
if(node->child)
{
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
printtree_r(node->child, depth +1);
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
for(i=0;i<depth*3;i++)
printf(" ");
printf("%s\n", node->data.c_str());
node = node->next;
}
}
}
void printtree(node *root)
{
printree_r(root, 0);
}
Para comprobar si dos árboles binarios son iguales o no.
- Por ejemplo si las entradas son:
Ejemplo 1
una)
segundo)
La salida debe ser verdadera.
Ejemplo: 2
Si las entradas son:
una)
segundo)
La salida debe ser falsa.
Seudo código para el mismo:
boolean sameTree(node root1, node root2){
if(root1 == NULL && root2 == NULL)
return true;
if(root1 == NULL || root2 == NULL)
return false;
if(root1->data == root2->data
&& sameTree(root1->left,root2->left)
&& sameTree(root1->right, root2->right))
return true;
}