I grafteori er et rodfæstet træ eller arborescens en rettet acyklisk graf med en enkelt rod og sådan, at alle knudepunkter undtagen roden har en enlig forælder.
I datalogi er det også en rekursiv datastruktur, der bruges til at repræsentere denne type graf.
I et træ er der to kategorier af elementer:
Den Roden af træet er den eneste node, der ikke har en forælder. Knudepunkterne (fædre med deres sønner) er forbundet med hinanden ved en højderyg . Afhængigt af konteksten kan en knude henvise til en intern eller ekstern knude (træ) i træet.
Den dybde af et knudepunkt er afstanden, dvs. antallet af kanter, fra roden til knudepunktet. Den Højden af et træ er den største dybde af et blad på træet. Den størrelse af et træ er dens antal knuder (tælle blade eller ikke), vejlængden er summen af dybet af hvert af bladene.
Træer kan mærkes. I dette tilfælde har hver knude en etiket , som er en slags "indhold" i noden. Etiketten kan være meget enkel: for eksempel et heltal. Det kan også være så komplekst, som du vil: et objekt, en forekomst af en datastruktur, en markør osv. Det er næsten altid obligatorisk at kunne sammenligne etiketterne i forhold til den samlede orden for at implementere algoritmerne på træerne.
Filer og mapper i et filsystem er normalt organiseret i en træstruktur. Se for eksempel FHS .
Træer bruges faktisk sjældent som sådan, men der findes mange typer træer med en mere restriktiv struktur og bruges ofte i algoritmer , især til administration af databaser eller til indeksering af filer. De tillader derefter hurtige og effektive søgninger. Her giver vi dig de vigtigste eksempler:
For at bygge et træ fra kasser, der kun indeholder information, kan du gøre en af følgende tre måder:
Vi bemærker, at der er andre typer repræsentation, der er specifikke for bestemte tilfælde af træer. For eksempel er bunken repræsenteret af en række etiketter.
De træ vandreture er knudepunkter besøg behandle af et træ, for eksempel for at finde en værdi.
Den bredde sti svarer til en bane ved niveau af knudepunkter af træet. Et niveau er et sæt interne noder eller blade placeret i samme dybde - vi taler også om en node eller et blad af samme højde i det betragtede træ. Gennemsøgningsrækkefølgen på et givet niveau tildeles normalt rekursivt af gennemsøgningsrækkefølgen af overordnede noder - noder på det næste højere niveau.
Hvis der således anvendes den tidligere træet, vil ruten være A , B , C , D , E , F og G .
Den dybtgående rute er en rekursiv rute på et træ. I det generelle tilfælde er to ordrer mulige:
For binære træer kan vi også foretage en infix-sti , det vil sige behandle den aktuelle knude mellem venstre og højre knudepunkt. Hvis der således anvendes den tidligere træet, vil ruten være D , B , E , A , F , C og G .