RAZLIKA MED POLNIM IN POPOLNIM BINARNIM DREVESOM

Binarno drevo

Obstajajo različne vrste binarnega drevesa ampak tukaj bomo razpravljali o razliki Popolno binarno drevo in Polno binarno drevo .

Celotno binarno drevo:

Polno binarno drevo je binarno drevo, v katerem vsa vozlišča imajo 0 ali 2 potomca . Z drugimi besedami, polno binarno drevo je binarno drevo, v katerem imajo vsa vozlišča, razen listnih vozlišč, dva potomca.

Polno binarno drevo

Pustiti, jaz je število notranjih vozlišč
n skupno število vozlišč
l biti število listov
l biti število stopenj

potem,

Število listov je (i + 1) .
Skupno število vozlišč je (2i + 1) .
Število notranjih vozlišč je (n – 1) / 2 .
Število listov je (n + 1) / 2 .
Skupno število vozlišč je (2l – 1) .
Število notranjih vozlišč je (l – 1) .
Število listov je največ (2^l- 1) .

Celotno binarno drevo:

Binarno drevo se imenuje a popolno binarno drevo če imajo vse njegove ravni, razen morebiti zadnje ravni, največje možno število vozlišč in vsa vozlišča v zadnja stopnja se prikaže čim bolj levo .

Popolno binarno drevo

Tu lahko prepoznate 2 točki,

Najprej mora biti vedno zapolnjena skrajna leva stran listnega vozlišča.

Ni nujno, da ima zadnje listno vozlišče pravega sorodnika.

Oglejte si naslednje primere, da boste bolje razumeli celotno binarno drevo.

Primer 1:

Niti popolna niti polna

Vozlišče C ima torej samo enega otroka, ni polno binarno drevo.

Vozlišče C ima torej tudi desnega otroka, ne pa tudi levega otroka prav tako ni popolno binarno drevo.

Zato je zgoraj prikazano binarno drevo ne popolno ne polno binarno drevo.

Primer 2:

Polno, vendar ne popolno

Vsa vozlišča imajo bodisi 0 oz 2 potomci torej, je polno binarno drevo .
To ni popolno binarno drevo, ker vozlišče B nima otrok, medtem ko vozlišče C ima otroke in v skladu s popolnim binarnim drevesom je treba vozlišča zapolniti iz leva stran .

Zato je zgoraj prikazano binarno drevo a Polno binarno drevo in je ni popolno binarno drevo.

Primer 3:

Popoln, vendar ne poln

Je popolno binarno drevo, saj so vsa vozlišča zapolnjena.
Vozlišče B ima samo enega otroka, torej ni polno binarno drevo.

Zato je zgoraj prikazano binarno drevo a Popolno binarno drevo in je ni polno binarno drevo.
konstruktor v Javi

Primer 4:

Popoln in poln

Je Popolna binarnost drevo, ker so vsa vozlišča ostalo zapolnjeno .

Vsa vozlišča imajo bodisi 0 oz 2 potomci, torej je a polno binarno drevo .

Zato je zgoraj prikazano binarno drevo tako popolno kot polno binarno drevo.

da ne	Popolno binarno drevo	Polno binarno drevo
1.	V popolnem binarnem drevesu ima lahko vozlišče na zadnji ravni samo enega otroka.	V polnem binarnem drevesu vozlišče ne more imeti samo enega otroka.
2.	V celotnem binarnem drevesu mora biti vozlišče zapolnjeno od leve proti desni.	V polnem binarnem drevesu ni vrstnega reda zapolnjevanja vozlišč.
3.	Popolna binarna drevesa se večinoma uporabljajo v podatkovnih strukturah, ki temeljijo na kopici.	Celotno binarno drevo nima uporabe kot tako, ampak se imenuje tudi pravilno binarno drevo.
4.	Popolno binarno drevo imenujemo tudi skoraj popolno binarno drevo.	Popolno binarno drevo, imenovano tudi pravilno binarno drevo ali 2-drevo.
5	Celotno binarno drevo mora imeti celotno vozlišče listov v popolnoma enaki globini.	Pri polnem binarnem drevesu ni nujno, da je raven listov v isti globini.

TechCodeview