C/Traballar con árbores: Diferenzas entre revisións
Contido eliminado Contido engadido
Artigo inicial. Continuará... |
Sen resumo de edición |
||
Liña 1:
{{Navegador
==Introdución á 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─.
Liña 6 ⟶ 7:
<source lang=c>
// Esta sería a versión mediante o uso dun ciclo:
signed long
{
signed long factorial = 1;
signed long
for(
factorial = factorial *
return factorial;
Liña 18 ⟶ 19:
// E estoutra sería a versión mediante programación recursiva:
signed long
{
if(
return 1;
else
return
}
</source>
As estruturas de datos recursivas ─que se van amosar a continuación─ só se poden utilizar mediante este tipo de programación. Son exemplos de estruturas recursivas as árbores ─que se van ver nesta páxina─ ou gráficos.
==Introdución ás á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.
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─.
==Árbores binarias==
Ás arbores binarias coteñ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.
Un exemplo da declaración dun nodo dunha árbore binaria sería o seguinte:
<source lang=c>
typedef struct estrutura
{
signed int dato;
struct estrutura * nodoesquerdo;
struct estrutura * nododereito;
}
estruturanodo;
</source>
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 esquera 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─.
Agora cómpre entendermos a eficiencia do uso de árbores binarias sobre o uso de listas encadeadas para certos casos. Imaxinemos que queremos ter en memoria unha lista cos datos: 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 20, 25, 35. Nunha lista estarían así, seguidos e ordeados. Nunha árbore estarían do seguinte xeito:
<pre>
10
/ \
7 15
/ \ / \
3 9 13 25
/ \ / / \ / \
1 5 8 12 14 20 35
</pre>
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.
E de cara á comprensión do funcionamento das árbores (binarias), cómpre botarlle outra ollada á árbore anterior, e pensar como quedaría en caso de que lle meteremos o valos <code>16</code>. A árbore quedaría entón así:
<pre>
10
/ \
7 15
/ \ / \
3 9 13 25
/ \ / / \ / \
1 5 8 12 14 20 35
/
16
</pre>
E se metésemos logo o valor <code>17</code>, e a continuación o valor <code>18</code>, e logo o <code>19</code>, a árbore quedaría desequilibrada, como xa se dixo. De aí a necesidade de equilibrar a árbore.
===Percorrer todos os nodos de árbores binarias===
Para visitar todos os nodos das árbores existen tres formas posibles:
*''Preorde''. Para cada nodo visítase a raíz, percórrese a árbore esquerda e logo a dereita. “RED”.
:''Para o exemplo anterior ─excluído o 17─, a orde quedaría: 10, 7, 3, 1, 5, 9, 8, 15, 13, 12, 14, 25, 20, 35.''
*''Inorde''. Para cada nodo visítase primeiro a raíz esquerda, lodo a raíz e logo a raíz dereita. “ERD”.
:''Para o exemplo anterior, a orde quedaría: 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 20, 25, 35.''
*''Postorde''. Para cada nodo visítase primeiro a raíz dereita, logo a esquerda e logo a raíz. “DER”.
:''Para o exemplo anterior, a orde quedaría: 35, 20, 25, 12, 14, 13, 15, 1, 5, 3, 8, 9, 7, 10.''
Nótese que o método ''inorde'' obtén os datos ordeados en función do valor que se utilizou para ordenar a árbore. Para que esta orde vaia á inversa, abondaría con facer un ''inorde'' inverso, é dicir, “DRE” en vez de “ERD”.
O percorrido ''postorde'' é o método que se utilizará á hora de borrar a árbore ─liberar o espazo que ocupa en memoria─.
==Notas==
Liña 37 ⟶ 108:
{{Navegador
[[Categoría:C ─ Dende cero|Arbores]]
| |||