DokuWiki

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.

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;
}

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.

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);
    }
}

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

   void insert (Item * & p, int k)

Prvni parameter je ukazatel a je predavany odkazem ( znak & ).
Pri volani

   insert (root, 7);

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.

    if (p == nullptr)
    {
        p = new Item;
        p->key = k;
        p->left = nullptr;
        p->right = nullptr;
    }

Pokud je klic ktery chceme vlozit v koreni prave zpracovaneho stromu. Nebudu delat nic. (Ale muzete ohlasit chybu.)

    else if (p->key == k)
    {
    }

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.

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

A podobne pro pravy podstrom. Zde je cela funkce.

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);
    }
}

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

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);
    }
}