zalg:nakresli_strom [ZC]

Nakresli strom

mxGraph https://jgraph.github.io/mxgraph/

#include <iostream>
#include <fstream>
 
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;
        }
    }
}
 
void print (Item* p)
{
    if (p != nullptr)
    {
        cout << p->key << endl;
        print (p->left);
        print (p->right);
    }
}
 
void writeNode (ofstream & f, Item * p, int x, int y, int sx, int sy)
{
    if (p != nullptr)
    {
        f << "    var v" << p->key << " = graph.insertVertex (parent, null, '" << p->key << "', " 
          << x << ", " << y << ", 80, 30);" << endl;
 
        if (p->left != nullptr)
        {
            writeNode (f, p->left, x-sx, y+sy, sx/2, sy);
            f << "    graph.insertEdge (parent, null, '', v" << p->key << ", v" << p->left->key << ");" << endl;
        }
        if (p->right != nullptr)
        {
            writeNode (f, p->right, x+sx, y+sy, sx/2, sy);
            f << "    graph.insertEdge (parent, null, '', v" << p->key << ", v" << p->right->key << ");" << endl;
        }
    }
}
 
void writeHtml (string fileName, Item * p)
{
    ofstream f (fileName);
 
    f << "<html>" << endl;
    f << "<head>" << endl;
    f << "<title>Tree with mxGraph</title>" << endl;
    f << "<script type=\"text/javascript\">" << endl;
    f << "    mxBasePath = 'http://jgraph.github.io/mxgraph/javascript/src';" << endl;
    f << "</script>" << endl;
    f << "<script type=\"text/javascript\" src=\"http://jgraph.github.io/mxgraph/javascript/src/js/mxClient.js\"></script>" << endl;
    f << "<script type=\"text/javascript\">" << endl;
 
    f << "function start (container)" << endl;
    f << "{" << endl;
    f << "    var graph = new mxGraph(container);" << endl;
    f << "    var parent = graph.getDefaultParent();" << endl;
    f << "    graph.getModel().beginUpdate();" << endl;
    f << endl;
 
    /*
    f << "    var v1 = graph.insertVertex (parent, null, 'a', 0, 0, 80, 30);" << endl;
    f << "    var v2 = graph.insertVertex (parent, null, 'b', 0, 0, 80, 30);" << endl;
    f << "    var e1 = graph.insertEdge (parent, null, '', v1, v2);" << endl;
    */
 
    if (p != nullptr)
    {
        writeNode (f, p, 400, 0, 200, 80);
    }
 
    f << endl;
    f << "    graph.getModel().endUpdate();" << endl;
    f << "};" << endl;
    f << "</script>" << endl;
    f << "</head>" << endl;
    f << "<body onload=\"start(document.getElementById('graphContainer'))\">" << endl;
    f << "<div id=\"graphContainer\">" << endl;
    f << "</div>" << endl;
    f << "</body>" << endl;
    f << "</html>" << endl;
 
    f.close ();
 
    string cmd = "\"C:/Program Files/Mozilla Firefox/firefox\" " + fileName;
    system (cmd.c_str());
}
 
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);
 
    writeHtml ("output1.html", root);
    remove (root, 10);
    writeHtml ("output2.html", root);
 
    /*
    remove (root, 12);
    remove (root, 3);
    remove (root, 7);
    */
 
    cout << "--------" << endl;
    print (root);
    cout << "--------" << endl;
 
    Item* t = lookup (root, 15);
    if (t != nullptr)
        cout << "Nasli " << t->key << endl;
    else
        cout << "Nenasli" << endl;
 
 
    cout << "O.K." << endl;
}

    writeHtml ("output1.html", root);
    remove (root, 10);
    writeHtml ("output2.html", root);

void writeNode (ofstream & f, Item * p, int x, int y, int sx, int sy)
{
    if (p != nullptr)
    {
        f << "    var v" << p->key << " = graph.insertVertex (parent, null, '" << p->key << "', " 
          << x << ", " << y << ", 80, 30);" << endl;
 
        if (p->left != nullptr)
        {
            writeNode (f, p->left, x-sx, y+sy, sx/2, sy);
            f << "    graph.insertEdge (parent, null, '', v" << p->key << ", v" << p->left->key << ");" << endl;
        }
        if (p->right != nullptr)
        {
            writeNode (f, p->right, x+sx, y+sy, sx/2, sy);
            f << "    graph.insertEdge (parent, null, '', v" << p->key << ", v" << p->right->key << ");" << endl;
        }
    }
}

void writeHtml (string fileName, Item * p)
{
    ofstream f (fileName);
 
    f << "<html>" << endl;
    /* ... */
    f << "<script type=\"text/javascript\" src=\"http://jgraph.github.io/mxgraph/javascript/src/js/mxClient.js\"></script>" << endl;
    /* ... */
    f << "<script type=\"text/javascript\">" << endl;
    /* ... */
 
    if (p != nullptr)
    {
        writeNode (f, p, 400, 0, 200, 80);
    }
 
    /* ... */
    f << "</script>" << endl;
    /* ... */
    f << "</html>" << endl;
 
    f.close ();
 
    string cmd = "\"C:/Program Files/Mozilla Firefox/firefox\" " + fileName;
    system (cmd.c_str());
}

Část souboru output1.html

    var v10 = graph.insertVertex (parent, null, '10', 400, 0, 80, 30);
    var v5 = graph.insertVertex (parent, null, '5', 200, 80, 80, 30);
    var v3 = graph.insertVertex (parent, null, '3', 100, 160, 80, 30);
    var v4 = graph.insertVertex (parent, null, '4', 150, 240, 80, 30);
    graph.insertEdge (parent, null, '', v3, v4);
    graph.insertEdge (parent, null, '', v5, v3);
    var v7 = graph.insertVertex (parent, null, '7', 300, 160, 80, 30);
    var v9 = graph.insertVertex (parent, null, '9', 350, 240, 80, 30);
    var v8 = graph.insertVertex (parent, null, '8', 325, 320, 80, 30);
    graph.insertEdge (parent, null, '', v9, v8);
    graph.insertEdge (parent, null, '', v7, v9);
    graph.insertEdge (parent, null, '', v5, v7);
    graph.insertEdge (parent, null, '', v10, v5);
    var v12 = graph.insertVertex (parent, null, '12', 600, 80, 80, 30);
    graph.insertEdge (parent, null, '', v10, v12);