==== Hledání prvku ve stromu ====

[[strom_2019_ut|zdrojový text]]

Funkce **search** je vlastne cyklus jdouci od korene dolu k listum. \\
Pokud najde hledany klic, vrati ukazatel na cely uzel stromu. \\
Pokud nenajde, vraci **nullptr**. \\
Parametrem je ukazatel na koren stomu a hodnota hledaneho klice.

Pokud zavolate search (root, 7), \\
zkopiruje se hodnota ukazatele z promenne **root** do parametru **p** \\
Parametr **p** mohu menit, aniz bych ovlivnil promennou **root**.

Konjunkce **&&** : \\
Pokud je levy parametr **false**, pravy parametr se jiz nevycisluje a vysledek je **false**. \\
V nasem pripade: pokud je **p** nulovy, vysledek vyrazu ''p != nullptr && p->key != k'' je **false** a cyklus se zastavi. \\
Pokud **p** neni nulovy, muzeme otestovat hodnotu ''p->key'' a zastavit, pokud potkame hledany klic.

<code C++>
Item * search (Item* p, int k) 
{
        while (p != nullptr && p->key != k) 
        {
            if (k < p->key)
                p = p->left;
            else
                p = p->right;
        }
        return p;
}
</code>

==== Rekurzivní hledání prvku ====

Rekuzivni varianta hledani prvku, funkce **find**. \\
Prvni paramater je ukazatel na koren podstromu, ve kterem hledame. \\
Pokud je podstrom prazdny vratime **nullptr**. \\
Ve zbyvajici casti funkce, je **p** nenulovy. \\
Pokud koren podstromu obsahuje hledany klic, vratime ukazatel na tento podstrom. \\
Pokud je kledany klic mensi nez hodnota v koreni, \\
pouzijeme rekurzivne funkci **find** na levy podstrom. \\
A co tato nova funkce vrati to bude i vysledkem nasi funkce. \\
** return find (p->left, k); **

Poznamka: slozene zavorky **{ }** uvnitr funkce nejsou nezbytne.\\
Za **if** nebo **else** nasleduje prave jeden prikaz.

<code C++>
Item * find (Item* p, int k)
{
    if (p == nullptr) 
    {
        return nullptr;
    }
    else if (p->key == k)
    {
        return p;
    }
    else if (k < p->key)
    {
      return find (p->left, k);
    }
    else
    {
       return find (p->right, k);
    }
}
</code>

Funkce **find** je jen slozitejsi variantou funkce **search**. \\
Pro hledani ji nejspise nebudeme pouzivat, ale poslouzi nam 
pri navrhu funkce pro vkladani.

==== Vkladani prvku do stromu ====

<code C++>
   void insert (Item * & p, int k)
</code>

Prvni parameter je ukazatel a je predavany odkazem ( znak **&** ).\\
Pri volani
<code C++>
   insert (root, 7);
</code>
se do paratetru **p** ulozi **odkaz** na promenou **root**. \\
Prekladac odkaz implementuje pomoci "skryteho" ukazatele ( v nasem pripade ukazatele opet na ukazatel. ) \\
Pokud promennou **p** menime, zmenime i obsah promenne **root**. Napr. //p = new Item;// \\
Pokud promennou **p** pouzivame, pouziva se obsah promenne **root**. Napr. //p == nullptr;// \\
Pokud cteme polozku **p**, pristupujeme k polozce **root**. Napr. //p->key == k;// \\

Pokud je strom prazdny, vytvorime **novou polozku** a jeji adresa je ulozena na misto kde bylo **nullptr** predstavujici nulovy koren puvodniho stromu.
<code C++>
    if (p == nullptr)
    {
        p = new Item;
        p->key = k;
        p->left = nullptr;
        p->right = nullptr;
    }
</code>

Pokud je klic ktery chceme vlozit v koreni prave zpracovaneho stromu. Nebudu delat nic. (Ale muzete ohlasit chybu.)
<code C++>
    else if (p->key == k)
    {
    }
</code>

Pokud je klic ktery chceme vlozit mensi nez hodnota v koreni prave zpracovaneho stromu, \\
rekurzivne zavolam funkci **insert**. \\
Jako paramatetr predam koren leveho podstromu. \\
Odkaz na levy podstrom se ulozi do parametru **p** nove zavolane funkce **insert**.

<code C++>
    else if (k < p->key)
    {
        insert (p->left, k);
    }
</code>

A podobne pro pravy podstrom.
Zde je cela funkce.

<code C++>
void insert (Item * & p, int k)
{
    if (p == nullptr)
    {
        p = new Item;
        p->key = k;
        p->left = nullptr;
        p->right = nullptr;
    }
    else if (p->key == k)
    {
    }
    else if (k < p->key)
    {
        insert (p->left, k);
    }
    else
    {
        insert (p->right, k);
    }
}
</code>

==== Varianty vkládání bez odkazu (reference), ale s ukazatelem na ukazatel. ====

Můžete porovnat s funkcemi **enter** a **ent**,
které používají dvojitý ukazatel. \\
( Jen pro ilustraci, nedoporucuji pouzivat. )

<code C++>
void enter (Item * * p, int k)
{
    if (*p == nullptr)
    {
        *p = new Item;
        (*p)->key = k;
        (*p)->left = nullptr;
        (*p)->right = nullptr;
    }
    else if ((*p)->key == k)
    {
 
    }
    else if (k < (*p)->key)
    {
        enter (&((*p)->left), k);
    }
    else
    {
        enter(&((*p)->right), k);
    }
}
 
void ent (Item * * p, int k)
{
    bool cont = true;
    while (cont)
    {
        if (*p == NULL)
        {
            *p = new Item;
            (*p)->key = k;
            (*p)->left = NULL;
            (*p)->right = NULL;
            cont = false;
        }
        else if ((*p)->key == k) cont = false;
        else if (k > (*p)->key)  p = &((*p)->right);
        else p = &((*p)->left);
    }
}
</code>