Wikibooks

C/Traballar con árbores: Diferenzas entre revisións

Explorar o historial de forma interactiva
← Edición máis vellaEdición máis nova →
Contido eliminado Contido engadido
VisualTexto wiki
Gallaecio (conversa | contribucións)
4.675 edicións
Amplío
Gallaecio (conversa | contribucións)
4.675 edicións
Amplío e realizo diversas modificacións.
Liña 2:
 
==Introdución á programación recursiva==
Antes de comezar a aprender o que son as árbores e como traballar con elas, cómpre coñecer un pouco por riba unha forma de programar moi empregada: a “programación recursiva”.
Hai unha forma de programar chamada “programación recursiva” ─moi empregada─. Disque cada función realiza unha tarefa completa, e para cada función deséñase un algoritmo. Unha función emprega programación recursiva cando se chama a si mesma ─ou máis exactamente, chama a unha función igual ca ela─.
 
Ata o momento as funcións que se programaron estaban escritas para ser chamadas por outras funcións ─ou polo sistema operativo no caso da función principal─ e asemade chamar a outras funcións. Existe un caso especial en que unha función se chama a si mesma ─ou máis exactamente, chama a unha función igual ca ela─. Neste caso estaremos falando de programación recursiva.
Un exemplo simple dunha función recursiva sería o dunha función para calcular o factorial<ref>O factorial dun número é a multiplicación de todos os números enterios entre 1 e el. Por exemplo, o factorial de 3 sería (1×2×3=) 6, o de 6 sería (1×2×3×4×5×6=) 720.</ref> dun número:
 
Un exemplo simple dunha función en que se pode empregar a programación recursiva sería o dunha función para calcular o factorial<ref>O factorial dun número é a multiplicación de todos os números enteiros entre 1 e o propio número. Por exemplo, o factorial de 3 sería (1×2×3=) 6, o de 6 sería (1×2×3×4×5×6=) 720.</ref> dun número. Seguindo o procedemento que se leva empregado ata o de agora, probablemente escribiríamos unha función como a seguinte para o cálculo do factorial:
<source lang=c>
// Esta sería a versión mediante o uso dun ciclo:
signed long CalcularOFactorial(signed long numero)
{
Liña 17 ⟶ 18:
return factorial;
}
</source>
 
Porén, a programación recursiva pode axudar aquí permitindo reducir a función ao seguinte código:
// E estoutra sería a versión mediante programación recursiva:
<source lang=c>
signed long CalcularOFactorial(signed long numero)
{
Liña 24 ⟶ 27:
return 1;
else
return nnumero * CalcularOFactorial(numero-1);
}
</source>
 
AsEste estruturastipo de datosprogramación recursivasé ─queo seque vanfai amosarposible ao continuación─ só se poden utilizar mediante este tipouso de programación. Son exemplosestruturas de estruturasdatos recursivas, coma as árbores ─queou seos van ver nesta páxina─gráficos (ou gráficos''grafos'').
 
==Introdución ás árbores==
Unha árbore é unha estrutura ─unha colección organizada de datos─ dinámica non lineal recursiva almacenada en memoria interna, formada por un conxunto de nodos e un conxunto de pólas. É dinámica porque se almacena en memoria dinámica, polo que o seu tamaño ─a cantidade de nodos que contén─ pode variar durante a execución dun programa. Non é lineal porque existe máis dun camiño posible entre un elemento da estrutura e outro. E é recursiva porque cada nodo da árbore é a raíz dunha nova árbore, «unha árbore é un conxunto de árbores».
Como toda estrutura de datos dinámica, as árbores constan dun punteiro que sinala á árbore, e cuxo valor será nulo ─<code>NULL</code>─ cando non haxa árbore.
 
Nunha árbore existe un nodo especial, a “raíz da árbore”, que é o único nodo de nivel 0, é dicir, é o que serve de referencia para toda a árbore, do que colgan o resto de nodos ou ''árbores subordinadas''. Como toda estrutura de datos dinámica, as árbores constan dun punteiro que sinala á árbore, e cuxo valor será nulo ─<code>NULL</code>─ cando non haxa árbore. Dito punteiro sinalará á raíz da árbore. Asemade, cada nodo da árbore ─incluída a raíz─ sinalará a unha certa cantidade de nodos subordinados a el.
Hai certos conceptos respecto das árbores que cómpre coñecer:
*Árbore binaria.
:Cada nodo da árbore contén dous nodos subordinados.
*Árbore equilibrada.
:Trátase de que non hai máis dun nivel de diferencia entre os nodos subordinados dunha árbore.
 
Cada nodo dunha árbore está formado polos datos ─a información que garda cada elemento, e que non variaría se en vez dunha árbore fose calquera outro tipo de estrutura─ e punteiros aos nodos directamente subordinados a el.
 
Os nodos finais, os que xa non teñen ningún nodo subordinado a eles, teñen a mesma estrutura que o resto dos nodos ─datos e punteiros aos nodos directamente subordinados─, coa diferencia de que os punteiros aos subordinados están baleiros ─non apuntan a ningures─.
 
Hai outros conceptos cos que cómpre familiarizarse antes de empezar a traballar con árbores:
==Árbores binarias==
*O número de pólas dun nodo denomínase “grao do nodo”.
Ás arbores binarias conteñen en cada nodo, ademais dos datos do elemento, dous punteiros, un a cada un dos seus nodos directamente subordinados. Podemos ver isto como se os subordinados estivesen cada un a un lado ─esquerdo e dereito─, posi probablemente axudará a visualizarmos a árbore á hora de traballar con ela.
*O “nivel dun nodo” nunha árbore equivale á distancia entre dito nodo e a raíz da árbore ─que ten nivel 0─.
*O nivel do nodo de maior nivel dunha árbore é a “altura da árbore”.
 
==Organización dunha árbore==
Un exemplo da declaración dun nodo dunha árbore binaria sería o seguinte:
Visto en que consiste unha árbore, cómpre agora entender de que maneira están ordenados os distintos nodos dunha árbore. Para iso utilizaremos como exemplo o caso dunha [[{{PAGENAME}}#Árbores binarias|árbore binaria]] ─que máis adiante se estudarán en profundidade─, que simplemente é unha árbore cuxos nodos sinalan a dous nodos subordinados.
<source lang=c>
typedef struct estrutura
{
signed int dato;
struct estrutura * nodoesquerdo;
struct estrutura * nododereito;
}
estruturanodo;
</source>
 
Chamando a estes dous nodos subordinados de cada nodo «esquerdo» e «dereito», e tomando como referencia un dato ou conxunto de datos concreto dos nodos ─por exemplo unha variable chamada “<code>dato</code>”─, cumprirase sempre que o <code>dato</code> do nodo subordinado esquerdo dun nodo será sempre inferior ao <code>dato</code> do nodo, e o <code>dato</code> do nodo subordinado dereito dun nodo será sempre superior ao <code>dato</code> do nodo.
Cómpre agora introducir o concepto de “árbore ordenada”, que no caso das árbores binarias se correspondería co caso en que os valores dos subordinados da esquerda son sempre inferiores que o nodo superior, e os valores dos subordinados da dereita son maiores que o nodo superior ─en función dun dato concreto ou unha combinación concreta de datos para cada nodo─.
 
AgoraPor cómpreexemplo, entendermosimaxínese aunha eficiencia do uso de árbores binarias sobre o uso de listas encadeadas para certos casos. Imaxinemosárbore que queremoscontén ter en memoria unha lista cosos datos: 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 20, 25, e 35. NunhaSeguindo listao estaríanenunciado así,no seguidosparágrafo eanterior, ordenados. Nunhaa árbore estaríanquedaría docoa forma seguinte xeito:
<pre>
10
Liña 70 ⟶ 61:
</pre>
 
==Eficiencia das árbores==
Durante unha busca de datos, a árbore binaria resultaría moito máis eficiente que a lista para esta busca. Cada comprobación permitirá desprezar directamente a metade dos datos da árbore, de aí a súa eficiencia. O problema é que a medida que se utilizan as árbores desequilíbranse ─algunhas das “raíces” quedan máis longas que outras─, polo que será necesario utilizar unha función para equilibralas.
Unha vez familiarizados coa forma en que se organizan os nodos dunha árbore, pódese comprender a eficiencia en certos casos ─especialmente á hora de buscar datos─ do uso de árbores ante, por exemplo, o uso de listas encadeadas. Visualícese a árbore binaria do [[{{PAGENAME}}#Organización dunha árbore|exemplo anterior]].
 
Durante unha busca de datos, a árbore binaria resultaría moito máis eficiente que a lista para esta busca. Cada comprobación na árbore permitirá descartar directamente a metade dos datos, de aí a súa eficiencia. Porén, na lista, se se buscase un dos últimos datos serían necesarias moitas comprobacións. Vexamos algúns números para o exemplo dado:
Para comprendermos o funcionamento das árbores (binarias), e máis concretamente o desequilibrio que provoca o seu uso (extracción e introdución de nodos), cómpre botarlle outra ollada á árbore anterior e intentar pensar como quedaría en caso de que se lle introducise outro nodo co valor <code>16</code>. A árbore quedaría entón así:
 
{| border="1px" cellspacing="0px" cellpadding="5px"
|Dato a buscar
|Comprobacións (lista)
|Comprobacións (árbore)
|-
|1
|1
|4
|-
|9
|6
|3
|-
|10
|7
|1
|-
|13
|9
|3
|-
|35
|14
|4
|}
 
==Percorrido dunha árbore==
Percorrer unha árbore consiste en visitar todos e cada un dos nodos que contén, de xeito que cada nodo se visite unha única vez. Este percorrido é posible mediante o uso de funcións recursivas.
 
As funcións para percorrer árbores variarán dependendo do grao da árbore, dos datos utilizados para organizar a árbore, así como da tarefa que se vaia realizar durante o percorrido ─gravar os datos en disco, borrar os nodos da árbore, etc.─.
 
==Desequilibrio==
O problema é que a medida que se utilizan, as árbores desequilíbranse ─algunhas das pólas quedan máis longas que outras─, polo que será necesario utilizar unha función para equilibralas.
 
Por exemplo, visualícese a árbore binaria que se utilizou previamente. Imaxínese como quedaría dita árbore en caso de inserir nela outro nodo co valor <code>16</code>. A árbore quedaría entón así:
<pre>
10
Liña 85 ⟶ 113:
</pre>
 
E en caso de meterlle a continuación outro nodo de valor <code>17</code>, e a continuación outro de valor <code>18</code>, e logo un de valor <code>19</code>, a árbore quedaría completamente desequilibrada,:
<pre>
como xa se dixo. De aí a necesidade de equilibrala. 10
/ \
7 15
/ \ / \
3 9 13 25
/ \ / / \ / \
1 5 8 12 14 20 35
/
16
\
17
\
18
\
19
</pre>
 
 
===Estrutura dun nodo===
==Árbores binarias==
A continuación amosarase unha declaración fundamental dun nodo para unha árbore binaria:
Ás arbores binarias conteñen en cada nodo, ademais dos datos do elemento, dous punteiros, un a cada un dos seus nodos directamente subordinados. Podemos ver isto como se os subordinados estivesen cada un a un lado ─esquerdo e dereito─, pois esta forma de visualizar as árbores binarias facilita a comprensión do funcionamento das funcións que traballan con elas.
 
===Declarar unha árbore binaria===
Para declarar unha árbore binaria é necesario, primeiro, definir a estrutura dos seus nodos, e segundo, declarar un punteiro a unha estrutura dese tipo. O valor inicial de dito punteiro debería ser nulo, de xeito que se poida saber durante a execución do programa se nun momento dado a árbore está baleira ou non.
 
O seguinte código define a estrutura dun nodo sinxelo que contén, ademais dos punteiros aos seus nodos subordinados, un único dato de tipo <code>signed int</code>:
<source lang=c>
typedef struct estruturadunnodoestruturasimpledunnodo
{
signed int dato // Neste caso o nodo só ten un dato.;
struct estruturadunnodoestruturasimpledunnodo * esquerdanodoesquerdo;
struct estruturadunnodoestruturasimpledunnodo * dereitanododereito;
}
estruturanodo;
</source>
 
Partindo desta estrutura, a declaración dunha árbore deste tipo realizaríase así:
===Crear un novo nodo===
<source lang=c>
estruturanodo * arbore;
</source>
 
Os seguintes exemplos de funcións para o traballo con árbores binarias utilizarán como base a estrutura aquí declarada.
 
===Crear un nodo binario===
Crear un nodo consiste en facer espazo en memoria para un novo nodo que vai ser [[{{PAGENAME}}#Inserir un nodo nunha árbore binaria|inserido nunha árbore]].
<source lang=c>
estruturanodo * NovoNodo(void)
{
// Declárase un punteiro ao novo nodo, con valor inicial nulo.
estruturanodo * novo;
estruturanodo * novo = NULL;
 
// Resérvase espazo en memoria dinámica para dito nodo.
novo = (estruturanodo *) malloc(sizeof(estruturanodo);
 
return novo; // ADevólvese o funciónenderezo devolveráde NULLmemoria seen nonque puidoestá reservarsituado o novo nodo.
return novo; // A función devolverá valor nulo se non puido reservar o novo nodo.
}
</source>
 
===Inserir un nodo nunha árbore binaria===
Inserir un nodo consiste en facer espazo para un novo nodo na árbore, encher o novo nodo cuns certos datos, e situar o nodo no lugar correcto da árbore en función dun deses datos ─ou conxunto de datos─, de xeito que a árbore quede organizada.
 
Nótese que os novos nodos sempre se colocan ao final das árbores, é dicir, colgando dun nodo pero sen que deles colgue nodo ningún.
<source lang=c>
signed short int InserirUnNodo(estruturanodo ** punteiroaarborepunteirosuperior, signed int dato)
{
estruturanodo * arbore = *punteirosuperior; // Recíbese o enderezo do nodo superior ou do punteiro á árbore se estaba baleira.
// Declaración de variables.
estruturanodo * arborenovo = *punteiroaarboreNULL; // RecíbesePunteiro ao novo nodo que se ávai árboreinserir.
signed short int control = 0; // Valor para controlar o correcto funcionamento da función.
estruturanodo * novo = NULL;
signed short int control = 0;
 
if(arbore == NULL) // ChegouseSe se chegou ao lugar ondedo que deberíavai ircolgar o novo nodo...
{
novo = NovoNodo(); // Solicítase...solicítase que se reserve un espazo en memoria para o nodo.
if(novo == NULL)
return -1; // Se ocorre un erro a función devolve -1;
else
{
// EncherDe se reservar o novoespazo nodoen dememoria información:correctamente,
// énchese o novo nodo coa información recibida pola función:
novo->dato = dato;
 
// e dáselles valor nulo aos punteiros aos seus nodos subordinados
// dado que os novos nodos nunca teñen subordinados.
novo->esquerda = NULL;
novo->dereita = NULL;
 
// “Colgar” oO nodo dasuperior árbore.ten que apuntar ao novo nodo.
*punteiroaarbore// =En novo;caso //de ...que sexa o seuprimeiro punteionodo apunteda aoárbore novoe non haxa nodo. superior,
// quen apuntará ao novo nodo será o punteiro á árbore.
*punteirosuperior = novo;
}
}
else // Se aínda non se chegou ao lugar do que vai colgar o novo nodo, séguese buscando.
else
{
if(arbore->dato < dato)
control = InserirUnNodo(&arbore->dereita,dato); // Ben pola dereita,
else
control = InserirUnNodo(&arbore->esquerda,dato); // ben pola esquerda.
}
 
// Se houbese algún erro durante o proceso de inserción do novo nodo,
// Saída da función.
// a función devolverá -1. Se todo marchou correctamente, devolverá 0.
return control;
}
Traído desde «https://gl.wikibooks.org/wiki/C/Traballar_con_árbores»