Skillnad mellan komplett binärt träd och fullt binärt träd

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 fullt binärt träd har l lämnar:

- Totalt antal noder n = 2 * l-1

- Antal interna noder i = l-1

Vad är komplett binärt träd?

Så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 bör också knutpunkter fästas från vänsterpositionen. Ett komplett binärt träd med höjd h uppfyller följande villkor:

- Från rotknutpunkten representerar nivån ovanför den sista nivån ett fullständigt binärt höjdhöjd h-1

- Ett eller flera noder på sista nivå kan ha 0 eller 1 barn

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

Vad är skillnaden mellan komplett binärt träd och fullt binärt träd?

Komplett 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.