Kas ir pilns binārais koks?
Pilnu bināro koku var definēt kā a binārais koks kurā visiem mezgliem ir 0 vai divi bērni. Citiem vārdiem sakot, pilnu bināro koku var definēt kā bināro koku, kurā visiem mezgliem ir divi bērni, izņemot lapu mezglus.
Tālāk redzamais koks ir pilns binārs koks:
Iepriekš minētais koks ir pilns binārs koks, jo visiem mezgliem, izņemot lapu mezglus, ir divi bērni.
java virknes vērtība
Pilna binārā koka teorēma:
Uzskatiet bināro koku T par tukšu koku, tad:
- Lai es būtu iekšējie mezgli kokā un L būtu lapas mezgls kokā, tad lapu mezglu skaits būtu vienāds ar:
L = I + 1 - Ja T ir, I iekšējo mezglu skaits un N ir kopējais mezglu skaits, tad kopējais mezglu skaits būtu vienāds ar:
N = 2I + 1 - Ja T satur “N” kopējo mezglu skaitu un “I” ir iekšējo mezglu skaits, tad iekšējo mezglu skaits būtu vienāds ar:
I = (N-1)/2 - Ja “T” ir “N” kopējais mezglu skaits un “L” ir lapu mezglu skaits, lapu mezglu skaits būtu vienāds ar:
L = (N+1)/2 - Ja “T” satur “L” lapu mezglu skaitu, tad kopējais mezglu skaits būtu vienāds ar:
N = 2L - 1 - Ja “T” ir “L” lapu mezglu skaits un “I” ir iekšējo mezglu skaits, tad iekšējo mezglu skaits būtu vienāds ar:
I = L - 1
Kas ir pilnīgs binārais koks?
Tiek uzskatīts, ka binārais koks ir pilnīgs binārais koks, ja visi līmeņi ir pilnībā aizpildīti, izņemot pēdējo līmeni, kas ir aizpildīts no kreisās puses.
Tālāk redzamais koks ir pilnīgs binārs koks:
Pilns binārais koks ir līdzīgs pilnajam binārajam kokam, izņemot divas atšķirības, kas norādītas zemāk:
- Lapu mezgla aizpildīšana jāsāk no vistālāk kreisās puses.
- Nav obligāti, ka pēdējās lapas mezglam jābūt pareizajam brālim.
Sapratīsim iepriekš minētos punktus, izmantojot piemēru:
Apsveriet tālāk redzamo koku:
Iepriekš minētais koks ir pilnīgs binārais koks, bet ne pilns binārais koks, jo 6. mezglam nav sava labā brāļa un māsas.
Pilnīga binārā koka izveide
Pieņemsim, ka mums ir 6 elementu masīvs, kā parādīts zemāk:
Iepriekš minētajā masīvā ir 6 elementi, t.i., 1, 2, 3, 4, 5, 6. Tālāk ir norādītas darbības, kas jāizmanto, lai izveidotu pilnīgu bināro koku:
1. darbība: Vispirms mēs atlasīsim pirmo masīva elementu, t.i., 1, un izveidosim koka saknes mezglu. Pirmajā līmenī pieejamo elementu skaits ir 1.
2. darbība: Tagad mēs atlasīsim otro un trešo masīva elementu. Saglabājiet otro un trešo masīva elementu kā saknes mezgla kreiso un labo atvasi, kā parādīts tālāk:
Kā mēs redzam iepriekš, otrajā līmenī pieejamo elementu skaits ir 2.
3. darbība: Tagad mēs atlasīsim nākamos divus elementus no masīva, t.i., 4 un 5. Saglabājiet šos divus elementus 2. mezgla kreisajā un labajā pusē, kā parādīts tālāk:
Kā mēs redzam iepriekš, mezgli 4 un 5 ir attiecīgi 2. mezgla kreisais un labais bērns.
4. darbība: Tagad mēs atlasīsim pēdējo masīva elementu, t.i., 6, un paturēsim to kā mezgla 3 kreiso atvasi, jo mēs zinām, ka pilnā binārajā kokā mezgli tiek aizpildīti no kreisās puses, kā parādīts zemāk:
Kā mēs varam novērot, ka otrais līmenis satur 3 elementus.
Izmantojot attēlus, sapratīsim atšķirības starp pilnīgu un pilnu bināro koku.
padarīt čaulas skriptu izpildāmu
- Tālāk redzamais binārais koks nav ne pilnīgs, ne pilns binārais koks. Tas nav pilns binārs koks, jo 3. mezglam ir tikai viens bērns. Tas arī nav pilnīgs binārais koks, jo mezgli ir jāaizpilda no kreisās puses, bet mezglam 3 ir labais bērns un nav kreisā bērna.
- Binārais koks, kas parādīts zemāk, ir pilns binārais koks, bet ne pilnīgs binārais koks. Tas ir pilns binārs koks, jo visiem mezgliem ir 0 vai 2 bērni. Tas nav pilnīgs binārais koks, jo 3. mezglam nav bērnu, savukārt 2. mezglam ir bērni, un mēs zinām, ka mezgli ir jāaizpilda no kreisās puses pilnā binārā kokā.
- Tālāk redzamais binārais koks ir pilnīgs binārais koks, bet ne pilns binārais koks. Tas ir pilnīgs binārais koks, jo visi mezgli ir atstāti aizpildīti. Tas nav pilns binārs koks, jo 2. mezglam ir tikai viens bērns.
- Tālāk redzamais binārais koks ir gan pilnīgs, gan pilns binārais koks. Tas ir pilnīgs binārais koks, jo visi mezgli ir atstāti aizpildīti. Tas ir pilns binārs koks, jo visiem mezgliem ir 0 vai 2 bērni.
