Oppgave 1

1. Treet har 6 nivåer
2. L, O, B
3. A, E, N, G
4. Et tre kan ha 2³ = 8 noder på nivå 3. Det er dermed plass til ytterligere 4 noder.
5. Et tre kan ha 2⁴ = 16 noder på nivå 4. Det er dermed plass til ytterligere 13 noder.
6. A-nodens etterkommere: K, F, C
7. A-nodens forgjengere: D, I, L
8. D, I, H, L, O, A
9. L, K
10. Treet har høyde 5.
11. Noden D har en dybde på 0.
12. I-nodens venstre subtre har høyde -1 og høyre subtre har høyde 3.
13. Treet har 7 bladnoder.
14. Treet har 15 noder totalt - 7 blanoder og 8 indre noder.

o. Et binærtre må ha minst én bladnode. F.eks. er enhver node på nederste nivå en bladnode. Det er lett å lage et tre med n noder som har bare én bladnode - f.eks. et såkalt ekstremt høyreskjevt tre, dvs. et tre der ingen noder har venstre barn. Hva er det maksimale antallet bladnoder et tre med n noder kan ha? Vi deler det i to tilfeller: 1) n et oddetall, dvs. n = 2k + 1 og 2) n et partall, dvs. n = 2k. Vi ser fort at et komplett tre med n noder der n = 2k + 1, vil ha k + 1 bladnoder. Finnes det noen trær med 2k + 1 noder som har flere enn k + 1 bladnoder? Det går en kant mellom hvert barn og dets forelder. Et binærtre må dermed ha nøyaktig n - 1 kanter, og hvis n = 2k + 1 blir det nøyaktig 2k kanter. Hvis det er flere enn k + 1 bladnoder må det være færre enn k indre noder. Det kan maksimalt gå to kanter nedover fra en indre node. Hvis det er færre enn k indre noder må det være færre enn 2k nedoverkanter. Men alle kanter kan ses på som nedoverkanter. Med andre ord en umulighet. Dvs. at k + 1 er det maksimale antallet bladnoder for et tre med n = 2k + 1 noder. Hvis vi har tilfellet 2), dvs. n = 2k, ser vi på en tilsvarende måte at det maksimale antallet bladnoder er lik k. Konklusjonen er derfor at det maksimale antallet bladnoder er lik ⌊n/2⌋.

Oppgave 2

1. Treet har 5 nivåer.
2. G, A, H, K
3. L, O, D, N
4. Et tre kan ha 2³ = 8 noder på nivå 3. Det er dermed plass til ytterligere 4 noder.
5. Et tre kan ha 2⁴ = 16 noder på nivå 4. Det er dermed plass til ytterligere 12 noder på nivå 4.
6. A-nodens etterkommere: L, O, M, C
7. A-nodens forgjengere: E, I
8. E, I, B, A, K
9. D, N
10. Treet har øyde 4
11. Noden D har en dybde på 3
12. I-nodens venstre subtre har høyde 0 og høyre subtre har høyde 2
13. Treet har 7 bladnoder
14. Treet har 15 noder totalt - 7 blanoder og 8 indre noder

Oppgave 3

1. En node kan ha maksimalt to søskenbarn. Nodene L, O og B har minst ett søskenbarn.
2. En node kan ha maksimalt fire tremenninger. Nodene A, E, N og G har minst en tremenning.

Oppgave 4

1. En node kan ha maksimalt to søskenbarn. Nodene G, A, H, K, D og N har minst ett søskenbarn.
2. En node kan ha maksimalt fire tremenninger. Nodene L, O, D og N som har minst en tremenning hver.

Oppgave 5

1. Treet i Oppgave 1 har diameter 9 og treet i Oppgave 2 har diameter 8.
2. Høyden er den største avstanden mellom rotnoden og en annen node. Diameter er største avstand mellom to noder. Dermed må diameter være minst så stor som høyden. Hvis f.eks. treet er ekstremt høyreskjevt (ingen node har venstre barn) vil høyde og diamter være like.
3. To søskennoder har en avstand på 2

d), e) og f)

Oppgave 6

Tre 1:
D I L A K F
D I L A K C
D I L E
D H O N M
D H O N J
D H O G
D H B

Tre 2:
E I G
E I A L
E I A O M
E I A O C
E B H D
E B K N J
E B K N F