Trädterminologi och regler

Träd är icke-linjära datastrukturer som beskriver hierarkier. Ett rotat träd har en bestämd rot. Varje annan nod har exakt en förälder, och varje kant sammanbinder två noder. Det finns exakt en enkel väg mellan två noder i ett träd. Till skillnad från vanliga grafer innehåller ett träd inga cykler.

Utforska begreppen interaktivt

Välj ett begrepp för att se vilka noder eller kanter det beskriver.

Markera ett begrepp

Hela trädetRotnodKanterNoderLövnoderBarnnoderFöräldranoderTrädets höjd (h = 2)Trädets storlek (n = 10)

Kontrollera din förståelse

Vad kallas noder som B, D, E, F, G, H och I, som inte har några barn?

RotnoderLövnoderFöräldranoderSyskonnoder

KontrolleraVisa förklaringNästa fråga

Välj ett begrepp och studera markeringen. R är roten, R, A och C är föräldranoder och B, D, E, F, G, H och I är löv. Detta är ett generellt träd, inte ett binärt träd, eftersom R har tre barn och C har fyra.

Djup, höjd och storlek

• Nodens djup: antalet kanter från roten. R har djup 0 och D har djup 2.
• Nodens höjd: antalet kanter på längsta nedåtgående vägen till ett löv. Ett löv har höjd 0.
• Trädets höjd: rotens höjd, alltså största djupet hos något löv. Här två kanter.
• Storlek: antal noder, här 10. Ett ändligt träd med 10 noder har exakt 9 kanter.
• Delträd: en nod tillsammans med alla dess efterkommande. Delträdet vid A innehåller A, D och E.

Vissa källor räknar nivåer från 1 i stället för djup från 0. Andra mäter höjd i noder i stället för kanter. Ange alltid vilken definition som används.

Relationer och användning

Syskon delar förälder, till exempel D och E. A och R är förfäder till D; F, G, H och I är efterkommande till C. Träd används i scenhierarkier, menyer, filsystem, syntaxträd och beslutsträd. En hierarki är bara ett träd om den följer reglerna om en förälder och inga cykler.

Kontrollera kunskaperna

Prova övningen och förutsäg markeringen för föräldrar, löv och trädets höjd. Förklara varför ett träd med n noder har n - 1 kanter: varje ny nod utom roten ansluts med exakt en kant.

Läs vidare

Trädegenskaper · Binära träd · Traversering

Referens: W3Schools om träd. Visualiseringen och övningen är egenutvecklade.