- Estructura jeràrquica amb nodes que tenen com a màxim dos fills; inclou arrel, fulles i nivells.
- Avantatges: cerques i insercions eficients, representacions jeràrquiques i flexibilitat dinàmica davant d'arrays.
- Operacions clau: recorreguts (in, pre, post), cerca, inserció i eliminació per ordenar i gestionar dades.
Benvinguts a aquesta guia completa sobre arbres binaris a C. En aquest article, explorarem els conceptes bàsics dels arbres binaris i com implementar-los en el llenguatge de programació C. Si ets un principiant en la programació o simplement vols millorar les teves habilitats a C, aquesta guia és per a tu.
Els arbres binaris són estructures de dades fonamentals en ciències de la computació i es fan servir en una àmplia gamma d'aplicacions. Comprendre com funcionen i com implementar-los us ajudarà a resoldre problemes complexos de manera més eficient i elegant.
Al llarg d'aquest article, explorarem els fonaments dels arbres binaris, incloent-hi la seva estructura, inserció i eliminació de nodes, recorreguts i cerca d'elements. També et proporcionarem exemples pràctics al llenguatge C perquè puguis veure com s'apliquen aquests conceptes a la pràctica.
Així que comencem!
Què són els arbres binaris?
Els arbres binaris són estructures de dades jeràrquiques compostes per nodes interconnectats. Cada node pot tenir fins a dos nodes secundaris: un a lesquerra i un altre a la dreta. Aquesta estructura de dues branques és allò que distingeix els arbres binaris d'altres estructures de dades.
En un arbre binari, el primer node s'anomena node arrel. Els nodes secundaris s'anomenen nodes fills, i els nodes sense fills s'anomenen nodes full. Els nodes al mateix nivell s'anomenen nodes germans.
Beneficis dels arbres binaris
Els arbres binaris ofereixen diversos avantatges en termes demmagatzematge i recerca eficient de dades. Alguns dels beneficis clau inclouen:
- Cerca eficient: Els arbres binaris permeten cercar elements en temps d'execució més ràpid que altres estructures de dades, com ara les llistes enllaçades. Això és degut a l'estructura jeràrquica de l'arbre i la seva capacitat per dividir ràpidament el conjunt de dades.
- Inserció i eliminació flexibles: Els arbres binaris són altament adaptables a les operacions dinserció i eliminació de nodes. A diferència de les estructures de dades estàtiques, com ara els arrays, els arbres binaris poden créixer i canviar la seva estructura dinàmicament.
- Representació de relacions jeràrquiques: Els arbres binaris són especialment útils per representar relacions jeràrquiques entre elements. Per exemple, en una estructura de directoris de fitxers, cada directori es pot representar com un node a l'arbre, amb subdirectoris i fitxers com els seus nodes fills.
Estructura d'un arbre binari
Abans d'endinsar-nos en la implementació dels arbres binaris a C, és important comprendre'n l'estructura bàsica. Cada node en un arbre binari conté un valor i referències als seus nodes fills esquerre i dret, si en té.
La taula següent mostra l'estructura d'un node en un arbre binari:
| Node binari |
|---|
| Valor |
| Node esquerre |
| Node dret |
Cada node pot emmagatzemar qualsevol tipus de dada, com ara enters, caràcters o estructures més complexes. El node arrel és el punt de partida de l'arbre, i hi podem accedir a tots els altres nodes.
Implementació d'arbres binaris a C
Ara que tenim una comprensió bàsica dels arbres binaris, és hora d'implementar-los al llenguatge de programació C . A continuació veurem com declarar i utilitzar una estructura d'arbre binari a C.
Declaració de l'estructura d'arbre binari
A C, podem declarar l'estructura d'un arbre binari utilitzant una estructura i punters. Aquí hi ha la declaració bàsica de l'estructura:
struct NodoArbol {
int valor;
struct NodoArbol* izquierdo;
struct NodoArbol* derecho;
};
En aquesta estructura, valor representa el valor emmagatzemat al node, i izquierdo y derecho són capdavanters als nodes fills esquerre i dret, respectivament.
Creació d'un nou node
Per crear un nou node a l'arbre binari, cal assignar memòria per al node i establir els seus valors. Aquí hi ha una funció a C que crea un nou node:
struct NodoArbol* crearNodo(int valor) {
struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
nodo->valor = valor;
nodo->izquierdo = NULL;
nodo->derecho = NULL;
return nodo;
}
la funció malloc s'utilitza per assignar memòria dinàmica al node. Després, configurem els valors del node i tornem el node creat.
Inserció de nodes
La inserció de nodes és un procés fonamental als arbres binaris. Permet afegir nous elements a l'arbre a la posició correcta segons el valor del node. A continuació es mostra una funció en C per inserir un node en un arbre binari:
struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
if (raiz == NULL) {
return crearNodo(valor);
}
if (valor < raiz->valor) {
raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
} else if (valor > raiz->valor) {
raiz->derecho = insertarNodo(raiz->derecho, valor);
}
return raiz;
}
Aquesta funció rep un punter a l'arrel de l'arbre i el valor del node que cal inserir. Si l'arrel és nul·la, vol dir que l'arbre és buit i creem un nou node a l'arrel. En cas contrari, comparem el valor del node amb el valor de l'arrel i decidim si cal inserir el node a l'esquerra oa la dreta.
Eliminació de nodes
L'eliminació de nodes en un arbre binari pot ser una mica més complexa. Depèn de diversos casos, com si el node a eliminar té fills o no. A continuació es mostra una funció en C per eliminar un node en un arbre binari:
struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
if (raiz == NULL) {
return raiz;
}
if (valor < raiz->valor) {
raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
} else if (valor > raiz->valor) {
raiz->derecho = eliminarNodo(raiz->derecho, valor);
} else {
if (raiz->izquierdo == NULL) {
struct NodoArbol* temp = raiz->derecho;
free(raiz);
return temp;
} else if (raiz->derecho == NULL) {
struct NodoArbol* temp = raiz->izquierdo;
free(raiz);
return temp;
}
struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
raiz->valor = sucesor->valor;
raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
}
return raiz;
}
En aquesta funció, verifiquem si el valor del node és menor, més gran o igual al valor de l'arrel actual. Depenent del cas, realitzem les accions següents:
- Si el valor és més petit, recorrem cap a l'esquerra de l'arbre.
- Si el valor és més gran, recorrem cap a la dreta de l'arbre.
- Si el valor és igual, trobem el successor més proper del node (el node més petit al subarbre dret) i el reemplacem pel node actual. Després, eliminem el successor del subarbre dret.
Recorreguts en arbres binaris
Els recorreguts són operacions que ens permeten visitar tots els nodes d‟un arbre binari en un cert ordre. Hi ha tres tipus comuns de recorreguts:
Recorregut en ordre (in-order) : Visita primer el subarbre esquerre, després el node actual i finalment el subarbre dret. Aquí hi ha una funció en C que fa un recorregut en ordre d'un arbre binari:
void inOrden(struct NodoArbol* raiz) {
if (raiz != NULL) {
inOrden(raiz->izquierdo);
printf("%d ", raiz->valor);
inOrden(raiz->derecho);
}
}
Recorregut en preordre (pre-ordre) : Visita primer el node actual, després el subarbre esquerre i finalment el subarbre dret. Aquí hi ha una funció en C que fa un recorregut en preordre d'un arbre binari:
void preOrden(struct NodoArbol* raiz) {
if (raiz != NULL) {
printf("%d ", raiz->valor);
preOrden(raiz->izquierdo);
preOrden(raiz->derecho);
}
}
Recorregut en posttorden (post-order) : Visita primer el subarbre esquerre, després el subarbre dret i finalment el node actual. Aquí hi ha una funció a C que fa un recorregut en posttorden d'un arbre binari:
void postOrden(struct NodoArbol* raiz) {
if (raiz != NULL) {
postOrden(raiz->izquierdo);
postOrden(raiz->derecho);
printf("%d ", raiz->valor);
}
}
Cerca d'elements
La cerca d'elements en un arbre binari ens permet trobar ràpidament un valor específic dins l'estructura de dades. Aquí hi ha una funció a C per cercar un element en un arbre binari:
struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
if (raiz == NULL || raiz->valor == valor) {
return raiz;
}
if (valor < raiz->valor) {
return buscarElemento(raiz->izquierdo, valor);
} else {
return buscarElemento(raiz->derecho, valor);
}
}
Aquesta funció fa una cerca recursiva a l'arbre binari. Si el valor del node actual és igual al valor cercat, es retorna el node. En cas contrari, es busca al subarbre esquerre o dret segons el valor i es repeteix el procés fins a trobar el valor o arribar a un node nul.
Exemples d'implementació d'arbres binaris a C
Ara que hem cobert els conceptes bàsics dels arbres binaris i com implementar-los a C, vegem alguns exemples pràctics.
Exemple 1: Creació d'un arbre binari
Suposem que volem crear un arbre binari amb els valors següents: 10, 5, 15, 3, 7, 13, 18. Aquí està com podem fer-ho a C:
int main() {
struct NodoArbol* raiz = NULL;
raiz = insertarNodo(raiz, 10);
raiz = insertarNodo(raiz, 5);
raiz = insertarNodo(raiz, 15);
raiz = insertarNodo(raiz, 3);
raiz = insertarNodo(raiz, 7);
raiz = insertarNodo(raiz, 13);
raiz = insertarNodo(raiz, 18);
return 0;
}
En aquest exemple, creem un punter a l'arrel de l'arbre i després fem servir la funció insertarNodo per afegir els valors a l'arbre.
Exemple 2: Recorregut en ordre de l'arbre binari
Per imprimir els valors de l'arbre binari en ordre, podem trucar a la funció inOrden de la següent manera:
int main() {
// Crear el árbol binario
printf("Recorrido en orden: ");
inOrden(raiz);
printf("\n");
return 0;
}
Aquest exemple imprimeix els valors de l'arbre en ordre ascendent.
Preguntes freqüents
1. Quina és la diferència entre un arbre binari i un arbre binari de cerca?
Un arbre binari de cerca (BST) és un tipus especial d'arbre binari on els elements s'organitzen de manera que els valors més petits es trobin a l'esquerra i els valors més grans a la dreta. Això permet una cerca més eficient d'elements en comparació amb un arbre binari regular.
2. Puc tenir nodes amb valors duplicats en un arbre binari?
Sí, és possible tenir nodes amb valors duplicats en un arbre binari. No obstant això, depenent de la implementació i les regles específiques de l'arbre binari, hi pot haver diferents maneres de tractar els nodes duplicats. Algunes implementacions poden permetre duplicats i emmagatzemar-los en qualsevol ordre, mentre que altres poden requerir que els valors duplicats es manegin de manera especial o es descartin.
3. Com puc eliminar un node específic d'un arbre binari?
Per eliminar un node específic d'un arbre binari, heu de seguir aquests passos:
- Troba el node que vols eliminar utilitzant una cerca a l'arbre.
- Considereu els diferents casos d'eliminació:
- Si el node no té fills, simplement el pots eliminar i alliberar la memòria.
- Si el node té un sol fill, podeu reemplaçar el node pel vostre fill.
- Si el node té dos fills, has de trobar el successor més proper (el node més petit al subarbre dret) i reemplaçar el valor del node a eliminar amb el valor del successor. Després elimina el successor de l'arbre.
- Ajusta els enllaços i els punters necessaris per mantenir l'estructura de l'arbre correcta.
4. Què és un arbre binari complet?
Un arbre binari complet és un tipus especial d'arbre binari on tots els nivells, excepte possiblement l'últim, estan completament plens, i els nodes de l'últim nivell es troben el més a l'esquerra possible. Això significa que tots els nodes tenen dos fills, excepte possiblement els nodes a l'últim nivell, que poden tenir un o cap fill.
5. Quina és lalçada dun arbre binari?
L'alçada d'un arbre binari és la llargada del camí més llarg des de l'arrel fins a una fulla. En altres paraules, és el nombre màxim d'arestes entre l'arrel i qualsevol fulla a l'arbre. L'alçada es mesura en termes de nombre de nivells, de manera que un arbre amb un sol node té una alçada de 0, i un arbre buit no té alçada.
6. Quan hauria d'utilitzar un arbre binari als meus programes?
Els arbres binaris són útils en diverses situacions. Alguns casos comuns en què podries utilitzar arbres binaris inclouen:
- Cerca eficient d'elements: Si necessiteu cercar elements ràpidament en una estructura de dades, un arbre binari pot proporcionar un accés eficient a les dades.
- Representació de relacions jeràrquiques: Els arbres binaris són ideals per representar relacions jeràrquiques, com l'estructura de directoris en un sistema d'arxius.
- Ordenació de dades: Pots utilitzar arbres binaris de cerca per ordenar dades de manera eficient i fer cerques, insercions i eliminacions en temps logarítmic.
Recorda avaluar els teus requisits i considerar la complexitat de les operacions en arbres binaris abans de decidir utilitzar-los als teus programes.
Conclusió
En aquesta guia completa, hem explorat els conceptes fonamentals dels arbres binaris a C. Hem après sobre la seva estructura, com inserir i eliminar nodes, fer recorreguts i buscar elements en un arbre binari.
Esperem que aquesta guia t'hagi proporcionat una comprensió sòlida dels arbres binaris i com implementar-los a C. Els arbres binaris són estructures de dades versàtils i poderoses que et poden ajudar a resoldre una àmplia gamma de problemes en la programació.
Recordeu practicar i experimentar amb els exemples proporcionats per enfortir la vostra comprensió dels arbres binaris en C. Bona sort en el vostre viatge d'aprenentatge i desenvolupament de programari!