===== Jednosměrný seznam =====

<code C++>
#include <iostream>
using namespace std;

struct Item
{
    string name;
    int    r, g, b;
    Item* next;
};

Item* first = nullptr; // prazdny seznam

void print(Item* t)
{
    cout << t->name << " " << t->r << "," << t->g << "," << t->b << endl;
}

Item * find (string name0)
{
    Item * p = first;
    while (p != nullptr && p->name != name0)
    {
        p = p->next;
    }
    return p;
}

int main()
{
    Item* c = new Item;
    c->name = "cervena";
    c->r = 255;
    c->g = 0;
    c->b = 0;

    Item* z = new Item;
    z->name = "zelena";
    z->r = 0;
    z->g = 255;
    z->b = 0;

    Item* m = new Item;
    m->name = "modra";
    m->r = 0;
    m->g = 0;
    m->b = 255;

    first = c;
    c->next = z; // za cervenou bude zelena
    z->next = m;
    m->next = nullptr; // za modrou nebude nic

    Item* u = first;
    while (u != nullptr)
    {
        print(u);
        u = u->next;
    }

    Item * t = find ("zelena");
    if (t == nullptr) 
        cout << "nenasli" << endl;
    else
        cout << "nasli " << t->name << ", " << t->r << ", " << t->g << ", " << t->b << endl;

    return 0;
}
</code>

{{seznam-ct.png}}


===== Binární strom =====

<code C++>
#include <iostream>
using namespace std;

struct Item
{
    int key;
    Item * left;
    Item * right;
    Item () : key (0), left (nullptr), right (nullptr) { }
};

Item* root = nullptr;

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

int main()
{
    Item* root = new Item;
    root->key = 7;

    Item* b = new Item;
    b->key = 5;
    root->left = b;

    Item* c = new Item;
    c->key = 3;
    b->left = c;

    Item* d = new Item;
    d->key = 10;
    root->right = d;

    cout << "O.K." << endl;
}
</code>

{{strom-ct.png}}


===== Vkládání prvku do stromu =====

<code C++>
#include <iostream>
using namespace std;

struct Item
{
    int key;
    Item * left;
    Item * right;
    // Item () { key = 0; left = nullptr; right = nullptr; }
    Item () : key (0), left (nullptr), right (nullptr) { }
};

Item* root = nullptr;

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

Item* lookup (Item* p, int value)
{
    if (p == nullptr)
    {
        return nullptr;
    }
    else if (p->key == value)
    {
        return p;
    }
    else if (value < p->key)
    {
        return lookup (p->left, value);
    }
    else
    {
        return lookup (p->right, value);
    }
}

void insert (Item * & p, int value)
{
    if (p == nullptr)
    {
        Item* t = new Item;
        t->key = value;
        p = t;
    }
    else if (p->key == value)
    {
    }
    else if (value < p->key)
    {
        insert (p->left, value);
    }
    else
    {
        insert (p->right, value);
    }
}

int main()
{
    insert (root, 7);
    insert (root, 5);
    insert (root, 3);
    insert (root, 10);
    insert (root, 12);

    insert (root, 12);

    Item* t = lookup (root, 12);
    if (t == nullptr)
        cout << "Nenasli" << endl;
    else
        cout << "Nasli " << t->key << endl;


    cout << "O.K." << endl;
}
</code>

{{strom-ct2.png}}

===== Tisk hodnot stromu =====

<code C++>
void print (Item* p)
{
    if (p != nullptr)
    {
        print (p->left);
        cout << p->key << endl;
        print (p->right);
    }
}
</code>

<code C++>
void print (Item* p, int level = 1)
{
    if (p != nullptr)
    {
        for (int i = 1; i <= level; i++) cout << "   ";
        cout << p->key << endl;
        print (p->left, level+1);
        print (p->right, level+1);
    }
}
</code>

===== Odstranění prvku ze stromu =====

<code C++>
void remove (Item * & p, int value)
{
    if (p == nullptr)
    {
    }
    else if (value < p->key)
    {
        remove (p->left, value);
    }
    else  if (p->key < value)
    {
        remove (p->right, value);
    }
    else /* p->key == value */
    {
        if (p->left == nullptr)
        {
            Item* t = p;
            p = t->right;
            delete t;
        }
        else if (p->right == nullptr)
        {
            Item* t = p;
            p = t->left;
            delete t;
        }
        else
        {
            /* dva podstromy */

            Item* u = p->left;
            while (u->right != nullptr)
                u = u->right;
        }
    }
}
</code>

<code C++>
int main()
{
    insert (root, 7);
    insert (root, 5);
    insert (root, 3);
    insert (root, 10);
    insert (root, 12);

    remove (root, 3);

    cout << "--------" << endl;
    print (root);
    cout << "--------" << endl;

    Item* t = search (root, 12);
    if (t == nullptr)
        cout << "Nenasli" << endl;
    else
        cout << "Nasli " << t->key << endl;

    cout << "O.K." << endl;
}
</code>