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

Contido eliminado Contido engadido
Gallaecio (conversa | contribucións)
Amplío
m Bot: Cambios estética
 
Liña 1:
{{Navegador|Traballar con listas encadeadas|Comentarios}}
 
== 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”.
 
Liña 33:
Este tipo de programación é o que fai posible o uso de estruturas de datos recursivas, coma as árbores ou os gráficos (ou ''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».
 
Liña 41:
 
Hai outros conceptos cos que cómpre familiarizarse antes de empezar a traballar con árbores:
* O número de pólas dun nodo denomínase “grao do nodo”.
* 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 ==
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.
 
Liña 61:
</pre>
 
== Eficiencia das árbores ==
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]].
 
Liña 92:
|}
 
== 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.─.
 
== Equilibrio ==
Unha árbore está equilibrada se para cada nodo o número de nodos que “colgan” de cada un dos seus nodos directamente subordinados non difiren os uns dos outros en máis dunha unidade.
 
Liña 136:
É por esta razón que ás veces, tras o seu uso continuado, adoita facerse necesario equilibrar as árbores.
 
== Árbores binarias ==
Á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.
 
Liña 160:
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>
Liña 176:
</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.
 
Liña 224:
</source>
 
=== Percorrer unha árbore binaria ===
Para percorrer todos os nodos das árbores existen tres formas posibles:
* ''Preorde''. Para cada nodo visítase primeiro a raíz, logo a árbore esquerda e logo a dereita. “RED”.
:''Para o exemplo inicial 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 árbore subordinada esquerda, lodo a raíz e logo a árbore subordinada dereita. “ERD”.
:Nótese que o método ''inorde'' obtén os datos ordenados 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”.
:''Para o exemplo inicial, 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 árbore subordinada dereita, logo a esquerda, e logo a raíz. “DER”.
:O percorrido ''postorde'' é o método que se utilizará á hora de borrar a árbore ─liberar o espazo que ocupa en memoria─.
:''Para o exemplo inicial, a orde quedaría: 35, 20, 25, 12, 14, 13, 15, 1, 5, 3, 8, 9, 7, 10.''
Liña 241:
Trátase de definicións recursivas, é dicir, a orde aplícase ao nodo raíz da árbore, pero tamén a todos os outros nodos (na orde estipulada pola propia definición).
 
==== Percorrido ''inorde'' dunha árbore binaria ====
A continuación preséntase un exemplo básico de percorrido da árbore polo método ''inorde''. Neste caso simplemente se imprimen os seus valores.
<source lang=c>
Liña 256:
</source>
 
=== Borrar unha árbore binaria ===
Unha forma de borrar unha árbore completa podería ser recorréndoa en ''postorde'':
<source lang=c>
Liña 270:
</source>
 
=== Equilibrar unha árbore binaria ===
Para crear unha árbore binaria perfectamente equilibrada realízase o seguinte proceso recursivo:
 
Liña 277:
::''<code>nodosdadereita = total - nodosdaesquerda - 1</code>''
:''E a continuación, para cada nodo:''
:* ''Xérase unha árbore subordinada esquerda cunha cantidade <code>nodosdaesquerda</code> de nodos.''
:* ''Utilízase o propio nodo.''
:* ''Xérase unha árbore subordinada dereita cunha cantidade <code>nodosdadereita</code> de nodos.''
:* ''Devólvese o enderezo do nodo.''
 
==== Crear unha árbore binaria equilibrada ====
Partindo dunha lista ordenada de datos pódese crear unha árbore equilibrada mediante unha función. esta función recibirá o número de elementos ou nodos a inserir na árbore. A función devolverá un punteiro á raíz da árbore construída. Vexamos un exemplo deste tipo de función:
<source lang=c>
Liña 316:
</source>
 
== Notas ==
<references />
 
== Véxase tamén ==
=== Exercicios ===
* [[{{BASEPAGENAME}}/Exercicios:Traballar con árbores|Exercicios de traballo con árbores]]