===== 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 * root = nullptr;

Item* search (Item* p, int value)
{
    while (p != nullptr && p->key != value)
    {
        if (value < p->key)
            p = p->left; /* search (p->left, value); */
        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()
{
    root = new Item;
    root->key = 7;

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

    //     7
    //   /
    //  5

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

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

    //         7
    //     /       \
    //    5 (a)     10 (b)
    //   /
    // 3 (c)           

    insert (root, 12);

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

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

{{strom-ct2.png}}


===== Vkládání prvku do stromu a výpis 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);
    }
}

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

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

    insert (root, 12);

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

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

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

{{strom-ct3.png}}

===== Vymazání prvku ze stromu =====

<code C++>

#include <iostream>
#include <iomanip> // setw

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

Item* findAndUnlink (Item * & u)
{
    if (u->right == nullptr)
    {
        Item* w = u;
        u = w->left;
        w->left = nullptr;
        return w;
    }
    else
    {
        return findAndUnlink (u->right);
    }
}

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 
    {
        // nasli jsme
        Item* t = p; // t ... k vymazani
        if (p->left == nullptr)
        {
            p = t->right;
            delete t;
        }
        else if (p->right == nullptr)
        {
            p = t->left;
            delete t;
        }
        else
        {
            // dva podstromy
            Item* u = findAndUnlink (t->left);
            u->left = t->left;
            u->right = t->right;
            p = u;
            delete t;

            /*
            Item* u = t->left; // nahradnik
            Item* m = nullptr; // minule u
            while (u->right != nullptr)
            {
                m = u;
                u = u->right;
            }

            if (m != nullptr)
               m->right = u->left;
            else 
               t->left = u->left;

            // u->left = nullptr;
            u->left = t->left;
            u->right = t->right;
            p = u;
            delete t;
            */

        }
    }
}

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

void show (Item* p, int level, int spaces, int & cnt, int inx = 1)
{
    if (p == nullptr)
    {
        if (inx <= level)
        {
            // doplnit mezery pro neexistujici vetve
            for (int i = 1; i <= 2*spaces; i++) cout << ' ';
        }
    }
    else
    {
        if (inx == level)
        {
            cout << setw (spaces) << p->key << setw (0);
            for (int i = 1; i <= spaces; i++) cout << ' ';
            cnt ++;
        }
        else if (inx < level)
        {
            show (p->left,  level, spaces/2, cnt, inx + 1);
            show (p->right, level, spaces/2, cnt, inx + 1);
        }
    }
}

void display (Item* p)
{
    int level = 1;
    int spaces = 64;
    bool stop = false;
    while (!stop)
    {
        int cnt = 0;
        show (p, level, spaces, cnt);
        if (cnt > 0)
        {
            cout << endl;
            level ++;
            // spaces /= 2;
        }
        else
        {
            stop = true;
        }
    }
}

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

    insert (root, 7);
    insert (root, 9);
    insert (root, 8);

    insert (root, 12);

    remove (root, 10);
    /*
    remove (root, 12);
    remove (root, 3);
    remove (root, 7);
    */

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

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

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

{{strom-ct4.png}}