C/Traballar con árbores: Diferenzas entre revisións
Contido eliminado Contido engadido
Sen resumo de edición |
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.
<pre>
10
Liña 85:
</pre>
E
===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==
|