Kahendpuu lehtede sisuks on arvud. Vaja on leida kõigi lehtede arvude

summa. Mis on vastava algoritmi keerukus olenevalt kahendpuu tippude

koguarvust n?

Mille leiab järgmine meetod etteantud kahendpuu puhul?

int leia(Tipp juur) {
    int vastus = 0;
    if (juur != null) {
        if (juur.vasak == null)
            vastus = 1;
        else
            vastus = leia(juur.vasak);
        vastus = vastus + leia(juur.parem);
    }
    return vastus;
}

Milline on parim andmestruktuur, mille abil kontrollida, kas

aritmeetilises avaldises, mis võib sisaldada kolme tüüpi sulge

Mitmel viisil saab avaldises

a+b-c-d+e

lisada kõigi tehete ümber sulud, et tehete sooritamise järjekord oleks

üheselt määratud?

Vastus:

Vihje: kahendpuu.

Kahendpuud võib kirja panna suluesitusena (X Y Z), mis tähendab, et tipu

X vasak ja parem alampuu on vastavalt Y ja Z. Seejuures võivad Y ja Z

olla omakorda suluesitused, kui vastavad alampuud olemas, või „null”, kui

alampuid ei ole. Lehte tähistab X ilma sulgudeta.

Millised järgmistest avaldistest on korrektsed kahendpuu suluesitused?

Antud on tasakaalus kahendpuu, mille kõik harud on sama pikkusega. Puu

iga tipu x puhul tuleb arvutada teatava funktsiooni g(x) väärtus ning

kirjutada see tippu x, käies niimoodi läbi kõik puu tipud. On teada, et

funktsiooni g(x) väärtuse arvutamise keerukus on võrdeline suurusega

min(x-i vasaku alampuu lehtede arv, x-i parema alampuu lehtede arv)

Mis on kahendpuu kõigi tippude väärtustega täitmise keerukus olenevalt

kahendpuu tippude arvust n?

Mille leiab järgmine meetod etteantud kahendpuu puhul?

int leia(Tipp juur) {
    if (juur == null)
        return 0;
    if (juur.vasak == null && juur.parem == null)
        return 1;
    return leia(juur.vasak) + leia(juur.parem);
}

Märgi kõik järjestused või nende kombinatsioonid, mille teadmisest

piisab, et kahendpuu üheselt taastada.