Què és un arbre binari complet?
Un arbre binari complet es pot definir com a arbre binari en què tots els nodes tenen 0 o dos fills. En altres paraules, l'arbre binari complet es pot definir com un arbre binari en el qual tots els nodes tenen dos fills excepte els nodes fulla.
L'arbre següent és un arbre binari complet:
L'arbre anterior és un arbre binari complet, ja que tots els nodes excepte els nodes fulla tenen dos fills.
Teorema complet de l'arbre binari:
Considereu que un arbre binari T és un arbre no buit:
- Sigui I nodes interns en un arbre i L sigui un node fulla en un arbre, aleshores el nombre de nodes fulla seria igual a:
L = I + 1 - Si T té, I nombre de nodes interns i N és el nombre total de nodes, aleshores el nombre total de nodes seria igual a:
N = 2I + 1 - Si T conté 'N' el nombre total de nodes i 'I' és el nombre de nodes interns, llavors el nombre de nodes interns seria igual a:
I = (N-1)/2 - Si 'T' té 'N' nombre total de nodes, i 'L' és un nombre de nodes fulla, llavors el nombre de nodes fulla seria igual a:
L = (N+1)/2 - Si 'T' conté el nombre 'L' de nodes fulla, llavors el nombre total de nodes seria igual a:
N = 2L - 1 - Si 'T' té 'L' nombre de nodes de fulla, i 'I' és un nombre de nodes interns, llavors el nombre de nodes interns seria igual a:
I = L - 1
Què és un arbre binari complet?
Es diu que un arbre binari és un arbre binari complet quan tots els nivells estan completament omplerts excepte l'últim nivell, que s'omple des de l'esquerra.
L'arbre següent és un arbre binari complet:
L'arbre binari complet és similar a l'arbre binari complet excepte per les dues diferències que es donen a continuació:
java booleà a cadena
- L'ompliment del node de la fulla ha de començar pel costat més esquerre.
- No és obligatori que l'últim node de fulla hagi de tenir el germà adequat.
Entenem els punts anteriors a través d'un exemple:
Considereu l'arbre següent:
L'arbre anterior és un arbre binari complet, però no un arbre binari complet, ja que el node 6 no té el seu germà dret.
Creació d'un arbre binari complet
Suposem que tenim una matriu de 6 elements que es mostra a continuació:
La matriu anterior conté 6 elements, és a dir, 1, 2, 3, 4, 5, 6. Els passos següents són els que s'han d'utilitzar per crear un arbre binari complet:
Pas 1: Primer, seleccionarem el primer element de la matriu, és a dir, 1, i farem un node arrel de l'arbre. El nombre d'elements disponibles al primer nivell és 1.
Pas 2: Ara, seleccionarem el segon i el tercer elements de la matriu. Mantingueu el segon element i el tercer element de la matriu com a fill esquerre i dret del node arrel, que es mostren a continuació:
Com podem observar més amunt que el nombre d'elements disponibles al segon nivell és 2.
Pas 3: Ara, seleccionarem els dos elements següents de la matriu, és a dir, 4 i 5. Mantingueu aquests dos elements a l'esquerra i a la dreta del node 2 que es mostren a continuació:
Com podem observar més amunt que els nodes 4 i 5 són els fills esquerre i dret del node 2 respectivament.
Pas 4: Ara, seleccionarem l'últim element de la matriu, és a dir, 6, i el mantindrem com a fill esquerre del node 3, ja que sabem que en un arbre binari complet, els nodes s'omplen des del costat esquerre que es mostra a continuació:
Com podem observar que el segon nivell conté 3 elements.
Entendrem les diferències entre l'arbre binari complet i complet a través de les imatges.
shreya ghoshal primer marit
- L'arbre binari que es mostra a continuació no és un arbre binari complet ni complet. No és un arbre binari complet perquè el node 3 només té un fill. Tampoc és un arbre binari complet, ja que els nodes s'han d'omplir des del costat esquerre, però el node 3 té un fill dret i no té un fill esquerre.
- L'arbre binari, que es mostra a continuació, és un arbre binari complet però no un arbre binari complet. És un arbre binari complet perquè tots els nodes tenen 0 o 2 fills. No és un arbre binari complet perquè el node 3 no té fills mentre que el node 2 té els seus fills i sabem que els nodes s'han d'omplir des del costat esquerre en un arbre binari complet.
- L'arbre binari que es mostra a continuació és un arbre binari complet però no un arbre binari complet. És un arbre binari complet ja que tots els nodes es queden plens. No és un arbre binari complet, ja que el node 2 només té un fill.
- L'arbre binari que es mostra a continuació és un arbre binari complet i complet. És un arbre binari complet ja que tots els nodes es queden plens. És un arbre binari complet ja que tots els nodes tenen 0 o 2 fills.
