Binärt träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 juli 2018; kontroller kräver 9 redigeringar .

Ett binärt träd  är en hierarkisk datastruktur där varje nod inte har fler än två avkomlingar (barn). Vanligtvis kallas den första noden föräldernoden, och barnen kallas för vänster och höger barn. Ett binärt träd är ett ordnat riktat träd [1] .

För praktiska ändamål används vanligtvis två undertyper av binära träd - ett binärt sökträd och en binär hög .

Rekursiv definition

Det finns följande rekursiva definition av ett binärt träd (se BNF ):

<binärt träd> ::= ( <data> <binärt träd> <binärt träd> ) | null .

Det vill säga, ett binärt träd är antingen tomt eller består av data och två underträd (som vart och ett kan vara tomt). Ett uppenbart men viktigt faktum att förstå är att varje delträd i sin tur också är ett träd. Om en nod har båda tomma underträden, så kallas den för en lövnod (bladvertex) eller lövnod (terminal) [2] .

Till exempel, som visas till höger i fig. 1 träd enligt denna grammatik skulle kunna skrivas så här:

(m (t.ex (c (en null null) null ) (g null (k null null) ) ) (s (p (o null null) (s null null) ) (y null null) ) )

Varje nod i trädet definierar ett underträd som det är roten till. Noden m = (data, vänster, höger) har två barn (vänster och höger) till vänster och höger och följaktligen två underträd (vänster och höger) med rötter till vänster och höger [3] .

Applikation

Många användbara datastrukturer är baserade på det binära trädet:

Anteckningar

  1. ↑ Binärt träd. . kvodo.ru. Hämtad 1 mars 2019. Arkiverad från originalet 2 mars 2019.
  2. ↑ Trä . Hämtad 1 mars 2019. Arkiverad från originalet 2 mars 2019.
  3. ↑ Binära sökträd: En introduktion . algolist.manual.ru. Hämtad 1 mars 2019. Arkiverad från originalet 14 juli 2019.

Länkar