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

Contido eliminado Contido engadido
Gallaecio (conversa | contribucións)
Sen resumo de edición
Gallaecio (conversa | contribucións)
Ampliado.
Liña 72:
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.
 
EPara decomprendermos cara á comprensión doo 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 meteremosintroducise ooutro nodo co valosvalor <code>16</code>. A árbore quedaría entón así:
<pre>
10
Liña 85:
</pre>
 
E seen metésemoscaso logode ometerlle a continuación outro nodo de valor <code>17</code>, e a continuación ooutro de valor <code>18</code>, e logo oun de valor <code>19</code>, a árbore quedaría completamente desequilibrada, como xa se dixo. De aí a necesidade de equilibrar a árboreequilibrala.
 
===Percorrer todos os nodos de árbores binarias===
Liña 99:
 
O percorrido ''postorde'' é o método que se utilizará á hora de borrar a árbore ─liberar o espazo que ocupa en memoria─.
 
===Estrutura dun nodo===
A continuación amosarase unha declaración fundamental dun nodo para unha árbore binaria:
<source lang=c>
typedef struct estruturadunnodo
{
signed int dato // Neste caso o nodo só ten un dato.
struct estruturadunnodo * esquerda;
struct estruturadunnodo * dereita;
}
estruturanodo;
</source>
 
===Crear un novo nodo===
<source lang=c>
estruturanodo * NovoNodo(void)
{
estruturanodo * novo;
 
novo = (estruturanodo *) malloc(sizeof(estruturanodo);
 
return novo; // A función devolverá NULL se non puido reservar o novo nodo.
}
</source>
 
===Inserir un nodo===
<source lang=c>
signed short int InserirUnNodo(estruturanodo ** punteiroaarbore, signed int dato)
{
// Declaración de variables.
estruturanodo * arbore = *punteiroaarbore; // Recíbese á árbore.
estruturanodo * novo = NULL;
signed short int control = 0;
 
if(arbore == NULL) // Se se chegou a onde se quería...
{
*punteiroaarbore = novo; // ...que o seu punteio apunte ao novo nodo.
 
novo = NovoNodo(); // Solicítase que se reserve un espazo en memoria para o nodo.
if(novo == NULL)
return -1;
else
{
// Encher o novo nodo de información:
novo->dato = dato;
novo->esquerda = NULL;
novo->dereita = NULL;
}
}
else
{
if(arbore->dato < dato)
control = InserirUnNodo(&arbore->dereita,dato);
else
control = InserirUnNodo(&arbore->esquerda,dato);
}
 
// Saída da función.
return control;
}
</source>
 
==Notas==