A
Un arbre binari
N'hi ha diferents tipus d'arbre binari però aquí parlarem de la diferència de Arbre binari complet i Arbre binari complet .
Arbre binari complet:
Un arbre binari complet és un arbre binari en el qual tots els nodes tenen 0 o 2 descendents . En altres termes, un arbre binari complet és un arbre binari en el qual tots els nodes, excepte els nodes fulla, tenen dos descendents.
Un arbre binari complet
Deixar, i sigui el nombre de nodes interns
n sigui el nombre total de nodes
l ser nombre de fulles
l ser nombre de nivellsun milió en xifresLlavors,
El nombre de fulles és (i + 1) .
El nombre total de nodes és (2i + 1) .
El nombre de nodes interns és (n – 1) / 2 .
El nombre de fulles és (n + 1) / 2 .
El nombre total de nodes és (2l – 1) .
El nombre de nodes interns és (l – 1) .
El nombre de fulles és com a màxim (2l– 1) .
Arbre binari complet:
Es diu que un arbre binari és a arbre binari complet si tots els seus nivells, excepte possiblement l'últim nivell, tenen el màxim nombre de nodes possibles, i tots els nodes del l'últim nivell apareix el més a l'esquerra possible .
Un arbre binari complet
Hi ha 2 punts que pots reconèixer des d'aquí,
- El costat més esquerre del node full sempre s'ha d'omplir primer.
- No és necessari que l'últim node de fulla tingui un germà correcte.
Comproveu els exemples següents per entendre millor l'arbre binari complet i complet.
Exemple 1:
Ni complet ni complet
- Node C per tant, només té un fill, no és un arbre binari complet.
- Node C també té un fill dret però no un fill esquerre, per tant tampoc és un arbre binari complet.
Per tant, l'arbre binari que es mostra a dalt és ni arbre binari complet ni complet.
Exemple 2:
Complet però no complet
- Tots els nodes en tenen 0 o 2 descendència, per tant, és un arbre binari complet .
No és un arbre binari complet perquè node B no té fills mentre que node C té fills i, segons un arbre binari complet, els nodes s'han d'omplir des del costat esquerre .Per tant, l'arbre binari que es mostra a dalt és a Arbre binari complet i ho és no és un arbre binari complet.
Exemple 3:
Complet però no complet
És un arbre binari complet ja que tots els nodes es queden plens.
- El node B només té un fill, per tant, no és un arbre binari complet.
Per tant, l'arbre binari que es mostra a dalt és a Arbre binari complet i ho és no és un arbre binari complet.
Exemple 4:
Complet i ple
- És un Binari complet arbre perquè tots els nodes ho són queda ple .
- Tots els nodes tenen qualsevol 0 o 2 descendència, per tant, és a arbre binari complet .
Per tant, l'arbre binari que es mostra a dalt és tant un arbre binari complet com un complet.
| S. No. | Arbre binari complet | Arbre binari complet |
| 1. | En un arbre binari complet, un node de l'últim nivell només pot tenir un fill. | En un arbre binari complet, un node no pot tenir només un fill. |
| 2. | En un arbre binari complet, el node s'ha d'omplir d'esquerra a dreta. | No hi ha cap ordre d'ompliment dels nodes en un arbre binari complet. |
| 3. | Els arbres binaris complets s'utilitzen principalment en estructures de dades basades en munts. | L'arbre binari complet no té cap aplicació com a tal, però també s'anomena arbre binari adequat. |
| 4. | Un arbre binari complet també s'anomena arbre binari gairebé complet. | Un arbre binari complet també anomenat arbre binari propi o arbre 2. |
| 5 | Un arbre binari complet ha de tenir tot el node de fulles exactament a la mateixa profunditat. | En ple nivell de fulla d'arbre binari no necessàriament ha d'estar a la mateixa profunditat. |