#include<iostream>
#include<string>

using namespace std;

struct node{
    char *d;
    node *left;
    node *right;
    };

class medis {
    node *first;
    void skleiskk (node *p);
    void clear (node **p);

public:

    medis () {first = NULL;}
    void put (char*);
    char * get (char*);
    void rodyk () {skleiskk(first);}
    ~medis () {clear(&first);}
};

void medis :: put ( char *e )
{
    node *t, *p = first;
    while (p)
    {
        t=p;
        if (strcmp(p->d,e) < 0)
            p = p->right;
        else p = p->left;
    };
    p = new node;
    p->d = e;
        p->left = p->right = NULL;
        if (!(first))
            first = p;
        else
            if (strcmp(t->d,e) < 0)
                t->right = p;
            else t->left = p;
}

char * medis :: get (char *p)
{
    node *m = first;
    while (m && strcmp(p, m->d))
        if (strcmp(p, m->d) > 0)
            m = m->right;
        else m = m->left;
    if (m)
        return m->d;
    else return NULL;
}

void medis :: skleiskk (node *p)
{
    if (p->left)
        skleiskk (p->left);
    cout << p->d << " ";
    if (p->right)
        skleiskk (p->right);
}

void medis :: clear (node **p)
{
    node *temp;
    if ((*p)->left)

        if ((*p)->left->left || (*p)->left->right)
            clear (&((*p)->left));
    if ((*p)->right)

        if ((*p)->right->left || (*p)->right->right)
            clear (&((*p)->right));
    temp = *p;
    *p = NULL;
    delete temp;
};

int main()
{

    medis A;

    char prad[] = "Zalias vynas ne vanduo, o studentas ne piemuo";
    char *p = strtok (prad, " ,");
    char *t, *z;
    while (p)
    {
        t = new char [strlen(p)+1];
        strcpy(t,p);
        A.put(t);
        p = strtok (NULL, " ,");
    }

    if (z = A.get("vynas"))
        cout << "Zodis " << z << " surastas" << endl;
    else
        cout << "Tokio zodzio medyje nera" << endl;
    cout << "Iskleisti medzio duomenys: " << endl;
    A.rodyk();
	cout << endl;
system("pause");
return 0;
}