zalg:strom_st [ZC]

Jednosměrný seznam

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

Binární strom

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

Vkládání prvku do stromu

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

Vkládání prvku do stromu a výpis stromu

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

Vymazání prvku ze stromu

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