Fullständigt binärt träd vs fullt 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 fler än två barn. I ett binärt träd namnges barn som "vänster" och "höger" barn. Undernoderna innehåller en referens till sin förälder. Ett komplett binärt träd är ett binärt träd där varje nivå i det binära trädet är helt fylld utom den sista nivån. I den ofyllda nivån är noderna fästa med början från positionen längst till vänster. Ett helt binärt träd är ett träd där varje nod i trädet har två barn utom trädets löv.
Vad är Full Binary Tree?
Fullständigt 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, varje nod i trädet utom löven har exakt två barn. Figur 1 nedan visar ett helt binärt träd. I ett helt binärt träd är antalet noder (n), antalet laver (l) och antalet interna noder (i) relaterade på ett speciellt sätt så att om du känner till någon av dem kan du bestämma de andra två värden enligt följande:
1. Om ett helt binärt träd har i interna noder:
– Antal blad l=i+1
– Tot alt antal noder n=2i+1
2. Om ett helt binärt träd har n noder:
– Antal interna noder i=(n-1)/2
– Antal blad l=(n+1)/2
3. Om ett helt binärt träd har l löv:
– Tot alt antal noder n=2l-1
– Antal interna noder i=l-1
Vad är Complete Binary Tree?
Som visas i figur 2 är ett komplett binärt träd ett binärt träd där varje nivå i trädet är helt fylld utom den sista nivån. På den sista nivån bör också noder fästas med början från positionen längst till vänster. Ett komplett binärt träd med höjd h uppfyller följande villkor:
– Från rotnoden representerar nivån över den sista nivån ett helt binärt träd med höjden h-1
– En eller flera noder i den senaste nivån kan ha 0 eller 1 barn
– Om a, b är två noder i nivån ovanför den sista nivån, så har a fler barn än b om och endast om a ligger till vänster om b
Vad är skillnaden mellan komplett binärt träd och fullt binärt träd?
Fullständiga binära träd och fullständiga binära träd har en tydlig 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 fullständigt binärt träd ett binärt träd där varje nivå i det binära trädet är helt fylld utom den sista nivån. Vissa speciella datastrukturer som heaps måste vara kompletta binära träd medan de inte behöver vara fullständiga binära träd. I ett helt binärt träd, om du vet antalet totala noder eller antalet laver eller antalet interna noder, kan du hitta de andra två mycket enkelt. Men ett komplett binärt träd har ingen speciell egenskap som relaterar dessa tre attribut.
