Классы и деревья

#include "stdafx.h"
#include "iostream"
#include <fstream>
#include <string>
using namespace std;
 
 
template <class Date>     //Шаблон класса для универсального типа хранимых данных
class Tree {
    struct node{
        string key;
        Date info;
        node *parent,*left,*right;
    };
 
private: 
    node *root;
    void printTree( node *root, int level=0 ){      
        if (root != 0){
            printTree( root->right, level + 1 );
            for ( int i = 0; i < level; i++ ) cout << "\t";
            cout << root->key <<endl;
            printTree( root->left, level + 1 );
        }
    };
    node * Leftmost( node *root ) {
        if (root == NULL)
            return NULL;
        if (root->left != NULL) {
            return Leftmost(root->left);
        }
        return root;
    };
    node * Rightmost( node *root ) {
        if (root == NULL)
            return NULL;
        if (root->right != NULL) {
            return Rightmost(root->right);
        }
        return root;
    };
 
 
public:
    //Обнуление указателя на корень
 
    Tree() {            
        this->root=0;
    };
 
    //Cоздание первого элемента
 
    void first( string Keyword, Date information ){     
        node *pf=new node;
        pf->key=Keyword;
        pf->info=information;
        pf->left=pf->right=pf->parent = 0;
        this->root=pf;
    };
 
    //Обход дерева
    void showTree(){         
        printTree( this->root, 0 );
    };
 
    //Добавление элемента(поиск места)
    node *addElement(string Key, Date information){
        node *pv = this->root,*prev;
        bool found = false;
        while ( pv && !found )
        {
            prev = pv;
            if ( pv->key == Key ) 
                found = true;
            else if ( pv->key > Key )
                pv = pv->left;
            else pv = pv->right;
        }
        if (found) {
            cout <<"Такой элемент уже существует"<<endl;
            return pv;
        }
 
        // Создание нового узла, если элемент не найден:
        node *pnew = new node;
        pnew->key=Key;
        pnew->info=information;
        pnew->left = 0;
        pnew->right = 0;
        pnew->parent = prev;
 
        if ( prev->key > Key )
            prev->left  = pnew;
        else
            prev->right = pnew;
 
        return pnew;
    };
 
    //Поиск
    node *search( string Key ){  
        node *pv = this->root;
        bool found = false;
        while ( pv && !found )
        {
            if ( pv->key == Key ) 
                found = true;
            else if ( pv->key > Key )
                pv = pv->left;
            else 
                pv  = pv->right;
        }
        if ( found )
            return pv;
        else return 0;
    };
 
    //Удаление корня
 
    void removeRoot(){
        node *r =this->root;
        if ( ( r->right == 0 ) && ( r->left == 0 ) )
        {   this->root = 0;
        delete (r);
        }
        else {
            this->root=Rightmost(r->left);
            this->root->parent=0;
 
            delete r; 
        }
    };
 
 
 
    //Удаление элемента
    void delElement( string Key ){
        node * n = search(Key); node *q;
        q=n;
        if ( n == 0 ){
            cout << "Value not found!" <<endl;
            return;
        }
        else if (n == this->root) {
            removeRoot();
        }
        else if (( n->left == 0) && (n->right == 0 )) {      //Если у элемента нету ни левого, ни правого ответвления
            if ( n->parent->left == n) 
                n->parent->left = 0;
            else      
                n->parent->right = 0;
            delete n;
        }
        else if ( n-> left == 0)  {
            n->right->parent = n->parent;
            if (n->parent->right == n)
            n->parent->right = n->right;
            else 
            n->parent->left = n->right;
            n=n->right;
            delete q;
        }
        else if ( n-> right == 0)  {
            n->left->parent = n->parent;
            if (n->parent->right == n)
            n->parent->right = n->left;
            else
            n->parent->left = n->left;
            n=n->left;
            delete q;
        }
        else{ 
            node *buf1, *buf2;
            node *f=Rightmost(n->left);
            if (n->parent->left == n) 
                n->parent->left = f;
            else n->parent->right = f;
            buf1=n->left;
            buf2=n->right;
            n=f;
            f->left=buf1;
            f->right=buf2;
            delete q;
 
        }
        cout << "Element has been seccessefully deleted" << endl;
    };
 
 
};
 
void ShowMenu(){
    system("cls");
    cout << " -------------------------------------------   " << endl;
    cout << "|     1. Create new tree                    |  " << endl;
    cout << "|     2. Read from keyboard                 |  " << endl;
    cout << "|     3. Read from file                     |  " << endl;
    cout << "|     4. Show translation of the word       |  " << endl;
    cout << "|     5. Delete element                     |  " << endl;
    cout << "|     6. Show the whole tree                |  " << endl;
    cout << "|     0. EXIT                               |  " << endl;
    cout << " -------------------------------------------   " << endl;
    cout << "Press number to continue                       " << endl;
};
 
int _tmain(int argc, _TCHAR* argv[]){
    setlocale(LC_ALL,"russian");     //Русская кодировка
    Tree <string> Slovar;
    string key,info;
    short int selector=255;
    for (;;){
        ShowMenu();
        cin >> (selector);
        switch (selector) {
        case 1: {
            string key,info;
            cout << "Enter word" << endl;
            cin >> key;
            cout << "Enter translation" << endl;
            cin >> info;
            Slovar.first(key,info);
            break;
                }
 
        case 2: { 
            short int i,j;
            cout <<"How much words you would like to add?" <<endl;
            cin >> j;
            for (i=0;i<j;i++) {
                cout << "Enter " << i+1 << " word" << endl;
                cin >> key;
                cout << "Enter " << key << " translation" << endl;
                cin >> info;
                Slovar.addElement(key,info);
            }
            break;
                }
 
        case 3: { 
            ifstream potok("note.txt");   // для работы со string'oм проще использовать stream, то есть поток; 
            string key,info;
            while(potok){
                getline(potok,key);
                getline(potok,info);
                if (Slovar.search(key) == 0 ){
                Slovar.addElement(key,info);
                }
            }
            break;
                }
 
        case 4: {
            string key;
            cout << "Enter the word" << endl;
            cin >> key;
            cout << key << " means " << Slovar.search(key)->info << endl;
            break;
                }
        case 5: {
            string key;
            cout << "Enter the word" << endl;
            cin >> key;
            Slovar.delElement(key);
            break;
                }
        case 6: {
            Slovar.showTree();
            break;
                }
        case 0: {
            return(0);
                }
        };
 
        system("pause");
    };
};

#include "iostream"
#include <fstream>
#include <string>
using namespace std;
 
 
template <class Date>     //Шаблон класса для универсального типа хранимых данных
class Tree {
    struct node{
        string key;
        Date info;
        node *parent,*left,*right;
    };
 
private: 
    node *root;
    void printTree( node *root, int level=0 ){      
        if (root != 0){
            printTree( root->right, level + 1 );
            for ( int i = 0; i < level; i++ ) cout << "\t";
            cout << root->key <<endl;
            printTree( root->left, level + 1 );
        }
    };
    node * Leftmost( node *root ) {
        if (root == NULL)
            return NULL;
        if (root->left != NULL) {
            return Leftmost(root->left);
        }
        return root;
    };
    node * Rightmost( node *root ) {
        if (root == NULL)
            return NULL;
        if (root->right != NULL) {
            return Rightmost(root->right);
        }
        return root;
    };
 
 
public:
    node *tmp; // для возврата значения с функции поиска
    //Обнуление указателя на корень
 
    Tree() {            
        this->root=0;
    };
 
    //Cоздание первого элемента
 
    void first( string Keyword, Date information ){     
        node *pf=new node;
        pf->key=Keyword;
        pf->info=information;
        pf->left=pf->right=pf->parent = 0;
        this->root=pf;
    };
 
    //Обход дерева
    void showTree(){         
        printTree( this->root, 0 );
    };
 
    //Добавление элемента(поиск места)
    node *addElement(string Key, Date information){
        node *pv = this->root,*prev;
        bool found = false;
        while ( pv && !found )
        {
            prev = pv;
            if ( pv->key == Key ) 
                found = true;
            else if ( pv->key > Key )
                pv = pv->left;
            else pv = pv->right;
        }
        if (found) {
            cout <<"Такой элемент уже существует"<<endl;
            return pv;
        }
 
        // Создание нового узла, если элемент не найден:
        node *pnew = new node;
        pnew->key=Key;
        pnew->info=information;
        pnew->left = 0;
        pnew->right = 0;
        pnew->parent = prev;
 
        if ( prev->key > Key )
            prev->left  = pnew;
        else
            prev->right = pnew;
 
        return pnew;
    };
 
    //Поиск
    node *search( string Key ){  
        tmp = this->root;
        bool found = false;
        while ( tmp && !found )
        {
            if ( tmp->key == Key ) 
                found = true;
            else if ( tmp->key > Key )
                tmp = tmp->left;
            else 
                tmp  = tmp->right;
        }
        if ( found )
            return tmp;
        else return 0;
    };
 
    //Удаление корня
 
    void removeRoot(){
        node *r =this->root;
        if ( ( r->right == 0 ) && ( r->left == 0 ) )
        {   this->root = 0;
        delete (r);
        }
        else {
            this->root=Rightmost(r->left);
            this->root->parent=0;
 
            delete r; 
        }
    };
 
 
 
    //Удаление элемента
    void delElement( string Key ){
        node * n = search(Key); node *q;
        q=n;
        if ( n == 0 ){
            cout << "Value not found!" <<endl;
            return;
        }
        else if (n == this->root) {
            removeRoot();
        }
        else if (( n->left == 0) && (n->right == 0 )) {      //Если у элемента нету ни левого, ни правого ответвления
            if ( n->parent->left == n) 
                n->parent->left = 0;
            else      
                n->parent->right = 0;
            delete n;
        }
        else if ( n-> left == 0)  {
            n->right->parent = n->parent;
            if (n->parent->right == n)
            n->parent->right = n->right;
            else 
            n->parent->left = n->right;
            n=n->right;
            delete q;
        }
        else if ( n-> right == 0)  {
            n->left->parent = n->parent;
            if (n->parent->right == n)
            n->parent->right = n->left;
            else
            n->parent->left = n->left;
            n=n->left;
            delete q;
        }
        else{ 
            node *buf1, *buf2;
            node *f=Rightmost(n->left);
            if (n->parent->left == n) 
                n->parent->left = f;
            else n->parent->right = f;
            buf1=n->left;
            buf2=n->right;
            n=f;
            f->left=buf1;
            f->right=buf2;
            delete q;
 
        }
        cout << "Element has been seccessefully deleted" << endl;
    };
 
 
};
 
void ShowMenu(){
    system("cls");
    cout << " -------------------------------------------   " << endl;
    cout << "|     1. Create new tree                    |  " << endl;
    cout << "|     2. Read from keyboard                 |  " << endl;
    cout << "|     3. Read from file                     |  " << endl;
    cout << "|     4. Show translation of the word       |  " << endl;
    cout << "|     5. Delete element                     |  " << endl;
    cout << "|     6. Show the whole tree                |  " << endl;
    cout << "|     0. EXIT                               |  " << endl;
    cout << " -------------------------------------------   " << endl;
    cout << "Press number to continue                       " << endl;
};
 
int main(){
    setlocale(LC_ALL,"russian");     //Русская кодировка
    Tree <string> Slovar;
    string key,info;
    short int selector=255;
    for (;;){
        ShowMenu();
        cin >> (selector);
        switch (selector) {
        case 1: {
            string key,info;
            cout << "Enter word" << endl;
            cin >> key;
            cout << "Enter translation" << endl;
            cin >> info;
            Slovar.first(key,info);
            break;
                }
 
        case 2: { 
            short int i,j;
            cout <<"How much words you would like to add?" <<endl;
            cin >> j;
            for (i=0;i<j;i++) {
                cout << "Enter " << i+1 << " word" << endl;
                cin >> key;
                cout << "Enter " << key << " translation" << endl;
                cin >> info;
                Slovar.addElement(key,info);
            }
            break;
                }
 
        case 3: { 
            ifstream potok("note.txt");   // для работы со string'oм проще использовать stream, то есть поток; 
            string key,info;
            while(potok){
                getline(potok,key);
                getline(potok,info);
                if (Slovar.search(key) == 0 ){
                Slovar.addElement(key,info);
                }
            }
            break;
                }
 
        case 4: {
            string key;
            cout << "Enter the word" << endl;
            cin >> key;
            cout << key << " means " << Slovar.search(key)->info << endl;
            break;
                }
        case 5: {
            string key;
            cout << "Enter the word" << endl;
            cin >> key;
            Slovar.delElement(key);
            break;
                }
        case 6: {
            Slovar.showTree();
            break;
                }
        case 0: {
            return(0);
                }
        };
 
        system("pause");
    };
}

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;
 
 
template <class Date>     //Шаблон класса для универсального типа хранимых данных
class Tree
{
public:
 
    struct node
    {
        node() : parent(0), left(0), right(0) {}
 
        node(string const& _key, Date const& _info) : key(_key), info(_info), parent(0), left(0), right(0) {}
 
        void insert(string const& _key, Date const& _info)
        {
            if(_key > key)
            {
                if(right)
                    right->insert(_key, _info);
                else
                {
                    right = new node(_key, _info);
                    right->parent = this;
                }
            }
            else if(_key < key)
            {
                if(left)
                    left->insert(_key, _info);
                else
                {
                    left = new node(_key, _info);
                    left->parent = this;
                }
            }
            else
                std::cerr << "Ключ уже существует\n";
        }
 
        string key;
        Date info;
        node *parent, *left, *right;
    };
 
    //Конструктор дерева
    Tree() : proot(0) {}
 
    //Обход дерева
    void showTree()
    {
        printTree( proot, 0 );
    }
 
    //Добавление уникального элемента
    void insert(string key, Date info)
    {
        if(!proot)
            proot = new node(key, info);
        else
            proot->insert(key, info);
    }
 
    //Поиск
    node *search( string Key )
    {
        node *pv = proot;
        bool found = false;
        while ( pv && !found )
        {
            if ( pv->key == Key )
                found = true;
            else if ( pv->key > Key )
                pv = pv->left;
            else
                pv  = pv->right;
        }
        return (found ? pv : 0);
    }
 
    //Удаление элемента
    void erase( string const& Key )
    {
        node * pfound = search(Key);
        if ( !pfound )
            cout << "Key not found" << endl;
        else // если узел в дереве найден
        {
            if(pfound->left)
            {
                node* prm = Rightmost(pfound->left);
                prm->right = pfound->right;
                pfound->left->parent = pfound->parent;
                if(pfound->parent)
                    pfound->parent->left == pfound ? pfound->parent->left = pfound->left : pfound->parent->right = pfound->left;
                else
                    proot = pfound->left;
                delete pfound;
                pfound = 0;
            }
            else if(pfound->right)
            {
                pfound->right->parent = pfound->parent;
                if(pfound->parent)
                    pfound->parent->left == pfound ? pfound->parent->left = pfound->right : pfound->parent->right = pfound->right;
                else
                    proot = pfound->right;
                delete pfound;
                pfound = 0;
            }
            else
            {
                if(pfound->parent)
                    pfound->parent->left == pfound ? pfound->parent->left = 0 : pfound->parent->right = 0;
                else
                    proot = 0;
                delete pfound;
                pfound = 0;
            }
            cout << "Element has been seccessefully deleted" << endl;
        }
    }
 
private:
    node *proot;
 
    void printTree( node *proot, int level=0 )
    {
        if (proot)
        {
            printTree( proot->right, level + 1 );
            for ( int i = 0; i < level; i++ ) cout << "\t";
            cout << proot->key << " - " << proot->info << endl;
            printTree( proot->left, level + 1 );
        }
    }
 
    node * Leftmost( node *proot )
    {
        if (proot->left)
            return Leftmost(proot->left);
        return proot;
    }
 
    node * Rightmost( node *proot )
    {
        if (proot->right)
            return Rightmost(proot->right);
        return proot;
    }
};
 
void ShowMenu()
{
    system("cls");
    cout << " -------------------------------------------   " << endl;
    cout << "|     1. Read from keyboard                 |  " << endl;
    cout << "|     2. Read from file                     |  " << endl;
    cout << "|     3. Translate word                     |  " << endl;
    cout << "|     4. Delete element                     |  " << endl;
    cout << "|     5. Show the whole tree                |  " << endl;
    cout << "|     0. EXIT                               |  " << endl;
    cout << " -------------------------------------------   " << endl;
    cout << "Input option: ";
};
 
int main()
{
    setlocale(LC_ALL,"rus");     //Русская кодировка
    Tree <string> Slovar;
    string key, info;
    short int selector = 255;
    while(true)
    {
        ShowMenu();
        cin >> (selector);
        switch (selector)
        {
            case 1:
            {
                string key, info;
                cout << "Enter word" << endl;
                cin >> key;
                cout << "Enter translation" << endl;
                cin >> info;
                Slovar.insert(key, info);
                break;
            }
            case 2:
            {
                ifstream ifs("dict.txt");   // для работы со string'oм проще использовать stream, то есть поток;
                if(ifs.is_open())
                {
                    string key, info;
                    while(ifs >> key >> info)
                        Slovar.insert(key, info);
                }
                else
                    std::cerr << "Unable to open input file\n";
                break;
            }
            case 3:
            {
                string key;
                cout << "Enter the word" << endl;
                cin >> key;
                Tree<string>::node* pfound = Slovar.search(key);
                if(pfound)
                    cout << key << " means " << pfound->info << endl;
                else
                    cout << "Key not found\n";
                break;
            }
            case 4:
            {
                string key;
                cout << "Enter the word" << endl;
                cin >> key;
                Slovar.erase(key);
                break;
            }
            case 5:
            {
                Slovar.showTree();
                break;
            }
            case 0:
                return 0;
        }
 
        system("pause");
    }
}