Strom vytvořený pomocí seznamů

#include <iostream>
#undef NDEBUG
#include <cassert>
using namespace std;
 
class Item
{
public:
    string name;
    int    r, g, b;
private:
    Item* above;
    Item* prev;
    Item* next;
    Item* first;
    Item* last;
public:
    Item* getAbove () { return above; }
    Item* getPrev () { return prev; }
    Item* getNext () { return next; }
    Item* getFirst () { return first; }
    Item* getLast () { return last; }
    bool empty () { return first == nullptr; }
 
private:
    void link (Item* before, Item* fresh, Item* after);
    void indent (int level);
public:
    void linkFirst (Item* fresh);
    void linkLast (Item* fresh);
    void linkBefore (Item* fresh);
    void linkAfter (Item* fresh);
 
    void insertFirst (string name0, int r0 = 255, int g0 = 255, int b0 = 255);
    void insertLast (string name0, int r0 = 255, int g0 = 255, int b0 = 255);
    void insertBefore (string name0, int r0 = 255, int g0 = 255, int b0 = 255);
    void insertAfter (string name0, int r0 = 255, int g0 = 255, int b0 = 255);
 
public:
    void unlink ();
 
    Item* find (string name0);
    Item* lookup (string name0);
    void  print (int level = 0);
 
    Item (string name0 = "", int r0 = 255, int g0 = 255, int b0 = 255); // konstruktor
    ~Item ();
 
    friend class Item;
};
 
Item::Item (string name0, int r0, int g0, int b0) :
    name (name0),
    r (r0),
    g (g0),
    b (b0),
    above (nullptr),
    prev (nullptr),
    next (nullptr),
    first (nullptr),
    last (nullptr)
{ }
 
Item :: ~Item ()
{
    if (above != nullptr)
        unlink ();
 
    Item* p = first;
    while (p != nullptr)
    {
        Item* t = p->next;
        delete p;
        p = t;
    }
}
 
void Item::link (Item* before, Item* fresh, Item* after)
{
    assert (before == nullptr || before->above == this && before->next == after); // before nulove nebo z naseho seznamu, nenulove before ma za naslednika after
    assert (after == nullptr || after->above == this && after->prev == before); // after nulove nebo z naseho seznamu, nenulove after ma za predchudce before
 
    assert (fresh != nullptr); // test zda fresh existuje
    assert (fresh->above == nullptr); // test zda fresh neni v zadnem seznamu
 
    fresh->above = this; // fresh zaradime do naseho seznamu
 
    fresh->prev = before;
    fresh->next = after;
 
    if (before != nullptr)
        before->next = fresh;
    else
        first = fresh;
 
    if (after != nullptr)
        after->prev = fresh;
    else
        last = fresh;
}
 
void Item::linkFirst (Item* fresh)
{
    this->link (nullptr, fresh, this->first);
}
 
void Item::linkLast (Item* fresh)
{
    link (last, fresh, nullptr);
}
 
void Item::insertFirst (string name0, int r0, int g0, int b0)
{
    this->linkFirst (new Item (name0, r0, g0, b0));
}
 
void Item::insertLast (string name0, int r0, int g0, int b0)
{
    linkLast (new Item (name0, r0, g0, b0));
}
 
void Item::linkAfter (Item* fresh)
{
    assert (above != nullptr);
    above->link (this, fresh, this->next);
}
 
void Item::linkBefore (Item* fresh)
{
    assert (above != nullptr);
    above->link (prev, fresh, this);
}
 
void Item::insertBefore (string name0, int r0, int g0, int b0)
{
    linkBefore (new Item (name0, r0, g0, b0));
}
 
void Item::insertAfter (string name0, int r0, int g0, int b0)
{
    linkAfter (new Item (name0, r0, g0, b0));
}
 
void Item::unlink ()
{
    assert (above != nullptr);
 
    Item* before = prev;
    Item* after = next;
 
    if (before != nullptr)
        before->next = after;
    else
        above->first = after;
 
    if (after != nullptr)
        after->prev = before;
    else
        above->last = before;
 
    prev = nullptr;
    next = nullptr;
    above = nullptr;
}
 
Item* Item::find (string name0)
{
    Item* p = first;
    while (p != nullptr && p->name != name0)
    {
        p = p->next;
    }
    return p;
}
 
Item* Item::lookup (string name0)
{
    Item* result = nullptr;
    Item* p = first;
    while (p != nullptr && result == nullptr)
    {
        if (p->name == name0)
            result = p;
 
        if (result == nullptr)
           result = p->lookup (name0);
 
        p = p->next;
    }
    return result;
}
 
void Item::indent (int level)
{
    for (int i = 1; i <= level; i++) cout << "    ";
}
 
void Item::print (int level)
{
    indent (level);
    cout << name << endl;
    if (not empty ())
    {
        indent (level);
        cout << "[" << endl;
        Item* t = first;
        while (t != nullptr)
        {
            t->print (level+1);
            t = t->next;
        }
        indent (level);
        cout << "]" << endl;
    }
}
 
int main ()
{
    Item b ("zivocichove"); // promenna pro nas seznam
    // Item * b = new Item ("zivocichove");
 
    b.insertLast ("selmy");
    b.insertLast ("sudokopytnici");
    b.insertLast ("lichopytnici");
 
    Item* t = b.find ("selmy");
    t->insertLast ("kockovite");
    t->insertLast ("psovite");
    t->insertLast ("medvedovite");
 
    t = t->find ("medvedovite");
    t->insertLast ("medved");
 
    b.print ();
 
    if (b.lookup ("psovite") != nullptr) cout << "nasli";
 
    return 0;
}