C/Traballar con árbores: Diferenzas entre revisións
Contido eliminado Contido engadido
m Cambios pequenos para mellorar a visualización da páxina. |
Amplío |
||
Liña 1:
{{Navegador|Traballar con listas encadeadas|Comentarios}}
==Introdución á programación recursiva==
Liña 97:
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.─.
==
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.
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.
Liña 131 ⟶ 133:
19
</pre>
É por esta razón que ás veces, tras o seu uso continuado, adoita facerse necesario equilibrar as árbores.
==Árbores binarias==
Liña 220 ⟶ 224:
</source>
===Percorrer
Para
*''Preorde''. Para cada nodo visítase primeiro a raíz,
:''Para o exemplo inicial
*''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.''▼
:''Para o exemplo anterior, a orde quedaría: 35, 20, 25, 12, 14, 13, 15, 1, 5, 3, 8, 9, 7, 10.''▼
*''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 ▲:''Para o exemplo
▲*''
:O percorrido ''postorde'' é o método que se utilizará á hora de borrar a árbore ─liberar o espazo que ocupa en memoria─.
▲:''Para o exemplo
Asemade podería considerarse unha cuarta forma de percorrer arbores binarias: ''inorde'' inversa. É o sentido inverso da forma ''inorde'' (“DRE”), e permite percorrer os valores da árbore ordenados de forma inversa, é dicir, en lugar de facelo dende o menor ao maior, farase dende o maior ao menor.
====Percorrido ''inorde''====▼
A continuación preséntase un exemplo básico de percorrido da aŕbore polo método ''inorde''. Neste caso simplemente se imprimen os seus valores.▼
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
<source lang=c>
// Esquerda, raíz, dereita. ERD.
Liña 248 ⟶ 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 259 ⟶ 267:
free(arbore);
}
}
</source>
===Equilibrar unha árbore binaria===
Para crear unha árbore binaria perfectamente equilibrada realízase o seguinte proceso recursivo:
:''Para un número “<code>total</code>” dado de nodos, sendo “<code>nodosdaesquerda</code>” o número de nodos á esquerda e “<code>nodosdadereita</code>” o número de nodos á dereita, calcúlase:''
::''<code>nodosdaesquerda = total / 2</code>''
::''<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>
estruturanodo * CrearUnhaArboreEquilibrada(signed int total)
{
signed int nodosdaesquerda, nodosdadereita; // Variables previamente enunciadas.
estruturanodo * novo = NULL; // Variable para almacenar os novos nodos.
if(total == 0) // Se non hai ningún valor a introducir na árbore.
return NULL; // Devólvese o valor nulo.
nodosdaesquerda = total / 2; // Calcúlanse os nodos da árbore subordinada esquerda,
nodosdadereita = total - nodosdaesquerda - 1; // e os da árbore subordinada dereita.
// Resérvase espazo en memoria dinámica para o novo nodo.
// Esta función xa se enunciou previamente máis arriba.
novo = NovoNodo();
// Créase ─de maneira equilibrada─ a árbore subordinada esquerda:
novo->nodoesquerdo = CrearUnhaArboreEquilibrada(nodosdaesquerda);
// Énchese de información este nodo.
// Neste exemplo non se meterá ningunha información, pero podería
// lerse a información dun ficheiro de xeito que se fose avanzando
// no ficheiro. O mesmo se aplica a unha pila ou unha cola.
// Créase ─de maneira equilibrada─ a árbore subordinada dereita:
novo->nododereito = CrearUnhaArboreEquilibrada(nodosdadereita);
// Devólvese o punteiro ao novo nodo.
return novo;
}
</source>
| |||