Puu (andmestruktuur): erinevus redaktsioonide vahel

Kahendpuu on selline puu, kus iga vanema võib olla mitteühtegimitte ühtegi, üks või kaks last ja laste järjekord on oluline.

Kahend-otsingupuu ([https://en.wikipedia.org/wiki/Binary_search_tree binary search tree]) on kahendpuu, mis on järjestatud. Tipust vasakul on alati väiksem suurus ja tipust paremal suurem suurus.<br>

Sellisest puust otsides võrreldakse otsitavat väärtust juurega, kui otsitav väärtus võrdub juure väärtusega, siis väärtus eksisteerib, kui aga juure väärtus ei võrdu otsitavaga, siis võrreldakse väärtust edasi, vastavalt kas vasaku või parema tippude hulgast kuni jõutakse leheni. Kui otsitav väärtus on võrdne mõne tipu väärtusega, siis on otsitav element olemas, kui aga ei leidu võrdset väärtust, siis otsitavat elementi ei ole. Selline otsimise viis on kordi kiirem kui oleks näiteks ahelloendi või massiivi läbivaatamine.<br>

Selle ülesande lahendus on näidatud kõrval oleval pildil, selline puu väljendab sellise avaldise tehete prioriteete. Sellise puuga antud avalise väärtuse leidmiseks on vaja osata läbida puud (rekursiivselt) lõppjärjestuses. Seega on selline rekursiivne tehnika ülioluline puude õppimisel. Materjalis kasutati seda näidet puude läbimise kolme nön-ö klassikaliste järgnevuste (lõppjärjekorda, eesjärjekorda ja keskjärjekorda) õpetamiseks. Selline meetod võib olla sobiv õpilasele, kes on varasemaltvarem puu struktuuriga kokku puutunud, kuid kui esimene tutvub esimest korda sellega, siis võib teema raskeks jääda. Näiteks on Tartu Ülikooli Arvutiteaduste instituudi poolt välja antud Algoritmide ja andmestruktuuride ülesannete kogus enne aritmeetilise avaldise puu ülesandeid pühendatud terve peatükk puu läbimisele ehk Tallinna Ülikooli materjalis on eeldatud, et õpilane suudab käigult ära õppida mõlemad teemad korraga.<ref> Ahti Peder, Jüri Kiho, Härmel Nestra (2017). "Algoritmid ja andmestruktuurid ülesannete kogu". </ref>

Puu tippudest informatsiooni lugemiseks tuleb need tipud kuidagi läbida. Kuna puu on rekursiivne struktuur, siis on seda ka mitmed algoritmid, mida nende peal rakendada saab. Seda tehakse rekursiivselt igale alampuule. Kui puud läbitakse, siis käiakse igas tipus täpselt üks kord. Kolm levinumat puu läbimiseks mõeldud algoritmi on järgmised:<br>

'''Eesjärjekord'''* eesjärjekord – väljastab kõigepealt juure, läbib terve vasaku alampuu ja seejärel läbib parema alampuu. Tuleb meeles pidada, et igal alampuul on oma juur, mida väljastada. Eelmise peatüki pildil olev puu annaks lahenduseks + / + B C A * D - E F.<br>;

'''Keskjärjekord'''* keskjärjekord – läbib kõigepealt vasaku alampuu, siis väljastab juure ja siis läbib parema alampuu (jälle tuleb meeles pidada, et igal alampuul on oma juur). SelliselSelle meetodilmeetodiga puud läbides annab sama puu lahenduseks B + C / A + D * E - F.<br>;

'''Lõppjärjekord'''* lõppjärjekord – läbib kõigepealt vasaku alampuu, siis läbib parema alampuu ja lõpuks väljastab juure alles. Sellel meetodil puud läbides tuleb sama puu lahenduseks B C + A / D E F - * +.

Graafi nimetatakse puuks, kui ta on sidus ja ei sisalda tsükleid. Mets on graaf, mile kõik komponendid on puud. Puu rippuvad tipud on lehed ja ülejäänud on sisetipud.<br>

Sidusa graafi toespuuks nimetatakse sellist alamgraafi, mis sisaldab kõiki tippe ja on puu. Tegu on andmestrutuurina väga olulise graafiga, sest toesuspuu albil saame rakendada mitmeid algoritme nagu Primi algoritm ja Kruskali algoritm. Nende abil saab leida lühimat teed läbides kõik antud punktid teel. <br>