Skillnad mellan komplett binärt träd och fullständigt binärt träd Komplett binärt träd vs full binärt träd binärt träd är

Komplett binärt träd vs full binärt träd

Binärt träd är ett träd där varje nod har ett eller två barn. I ett binärt träd kan en nod inte ha mer än två barn. I ett binärt träd heter barn som "vänster" och "rätt" barn. Barnnoden innehåller en hänvisning till deras förälder. Ett komplett binärt träd är ett binärt träd där varje nivå av binärträdet är helt fyllt utom den sista nivån. I den ofyllda nivån är knutarna fästa från början till vänster. Ett fullständigt binärt träd är ett träd där varje nod i trädet har två barn utom trädens löv.

Vad är fullt binärt träd?

Full binärt träd är ett binärt träd där varje nod i trädet har exakt noll eller två barn. Med andra ord har varje nod i trädet förutom bladen exakt två barn. Figur 1 nedan visar ett fullständigt binärt träd. I ett fullständigt binärt träd är antalet nodar (n), antal lag (l) och antalet interna noder (i) relaterade på ett speciellt sätt så att om du vet någon av dem kan du bestämma de andra två värden enligt följande:

1. Om ett fullständigt binärt träd har i interna noder:

- Antal blad l = i + 1

- Totalt antal noder n = 2 * i + 1

2. Om ett fullständigt binärt träd har n noder:

- Antal interna noder i = (n-1) / 2

- Antal blad l = (n + 1) / 2

3. Om ett fullständigt binärt träd har l blad:

- Totalt antal noder n = 2 * l-1

- Antal interna noder i = 1-1

Vad är komplett binärt träd?

Som visas i figur 2 är ett komplett binärt träd ett binärt träd där varje nivå av trädet är helt fylld utom den sista nivån. På den sista nivån borde också knutpunkter fästas från vänsterpositionen. Ett fullständigt binärt träd med höjd h uppfyller följande villkor:

- Från rotknutet representerar nivån ovanför den sista nivån ett helt binärt höjdhöjd h-1

- En eller flera noder i den sista nivån kan ha 0 eller 1 barn

- Om a, b är två noder i nivån ovanför den sista nivån, har a fler barn än b om och endast om a ligger till vänster om b

Vad är skillnaden mellan Complete Binary Tree och full binärt träd?

Kompletta binära träd och fulla binära träd har en klar skillnad. Medan ett fullständigt binärt träd är ett binärt träd där varje nod har noll eller två barn är ett komplett binärt träd ett binärt träd där varje nivå av binärträdet är helt fyllt utom den sista nivån. Vissa speciella datastrukturer som höjer måste vara kompletta binära träd medan de inte behöver vara fulla binära träd. I ett fullständigt binärt träd kan du hitta de andra två väldigt enkelt om du vet hur många totalt antal noder som är, antalet antal eller antal inre noder.Men ett komplett binärt träd har ingen speciell egenskap som relaterar dessa tre attribut.