Бинарное дерево

@Dedy111ka · Регистрация: 20.02.2019

Студворк — интернет-сервис помощи студентам

Здавствуйте, не работает удаление элемента в бинарном девере поиска.
Задание:
Задание:
Описать шаблон класса двоичное дерево поиска (BinSTree), представленное в виде многосвязного списка.
Реализовать основные операции, осуществляемые с бинарными деревьями поиска:
- создание бинарного дерева поиска;
- вставка элемента в бинарное дерево поиска;
- удаление элемента из бинарного дерево поиска;
- поиск элемента в бинарном дереве поиска;
- обход бинарного дерева поиска (указаны в варианте);
- вывод бинарного дерева поиска;
- проверка пустоты бинарного дерева поиска;
- удаление бинарного дерева поиска.
По желанию можно добавить другие операции.
Создать класс согласно своему варианту с перегруженной операцией < для задания критерия сравнения объектов данного класса и перегруженной операцией == для выполнения поиска (два объекта равны, если равны значения элементов-данных этих объектов).
Написать программу, демонстрирующую работу с этим шаблоном для типа int и для созданного класса. Программа должна содержать меню, позволяющее осуществить проверку всех операций.
Создать многомодульный проект.

C++

#include <iostream>
using namespace std;
 
class konus
{
private:
    double rad_osn;
    double h;
public:
    konus() {};
    konus(double rad_, double h_)
    {
        rad_osn = rad_;
        h = h_;
    }
    double pl_kon()
    {
        return 3.14 * rad_osn * rad_osn + 3.14 * rad_osn * sqrt((rad_osn * rad_osn) + (h * h));
    }
 
    friend bool operator < (konus, konus);
    friend bool operator ==(konus, konus);
 
    friend ostream& operator <<(ostream&, konus);
    friend istream& operator >>(istream&, konus&);
 
};
 
bool operator < (konus obj1, konus obj2)
{
    return (obj1.pl_kon() < obj2.pl_kon());
}
bool operator ==(konus obj1, konus obj2)
{
    return (obj1.pl_kon() == obj2.pl_kon());
}
 
istream& operator >> (istream& is, konus& obj1)
{
    cout << "vvedite" << endl;
    is >> obj1.rad_osn >> obj1.h;
    return is;
}
ostream& operator << (ostream& os, konus obj)
{
    cout << "vivod" << endl;
    os << obj.rad_osn << obj.h;
    return os;
}
 
template <class T>
 
 
class Bin_tree
{
 
public:
    T zn;// число в дерево
    Bin_tree* left; // указатель на левый
    Bin_tree* right; // указатель на правый
};
 
// поиск минимального
template <typename T>
Bin_tree<T>* getmin(Bin_tree<T>*& Tree)
{
 
    if (Tree == NULL)
    {
        return NULL;
    }
    if (Tree->left != NULL)
    {
        getmin(Tree->left);
    }
    else
    {
        return Tree;
    }
}
 
// удаление элем
template <typename T>
void udal_elem(Bin_tree<T>* tree, T b)
{
    if (tree != NULL)
    {
        if (b == tree->zn)
        {
            if ((tree->left == NULL) && (tree->right == NULL))
            {
                delete tree;
                tree = NULL;
 
            }
            else if (tree->left == NULL && tree->right != NULL)
            {
 
                tree = tree->right;
                tree->right = NULL;
 
            }
            else if (tree->left != NULL && tree->right == NULL) {
                tree = tree->left;
                tree->left = NULL;
 
            }
            else if (tree->left != NULL && tree->right != NULL)
            {
                Bin_tree<T>* ptr = getmin(tree->right);
                tree->zn = ptr->zn;
                udal_elem(tree->left, ptr->zn);
 
            }
 
        }
        else if (b < tree->zn)  //   c помощью 1 и 2 if идем влево 
            //потом вправо пока не найдем нужный элемент и не вызовем рекурсивную функцию
        {
            udal_elem(tree->left, b); // рекурсия 
        }
        else if (b > tree->zn)
        {
            udal_elem(tree->right, b); // рекурсия
        }
    }
    else
    {
        cout << " elementa net " << endl;
    }
}
 
// поиск
template <typename T>
void poisk(Bin_tree<T>* Tree, T a)
{
    if (Tree != NULL)
    {
        if (Tree->zn == a)
        {
            cout << "Элемент найден" << endl;
            return;
        }
        else if (a < Tree->zn)
        {
            poisk(Tree->left, a);
        }
        else if (a > Tree->zn)
        {
            poisk(Tree->right, a);
        }
 
    }
    else
    {
        cout << "net elementa" << endl;
    }
}
 
// обход пкл
template <typename T>
void PKL(Bin_tree<T>* Tree)
{
    if (Tree != NULL)
    {
        PKL(Tree->right);
        cout << Tree->zn << "\t";
        PKL(Tree->left);
    }
}
 
// обход клп
template <typename T>
void KLP(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        cout << tree->zn << "\t";
        KLP(tree->left);
        KLP(tree->right);
    }
}
 
// вставка элемента
template <typename T>
void vstavka(Bin_tree<T>*& TREE, T k)
{
    //1
    if (TREE == NULL)
    {
        TREE = new Bin_tree<T>;
        TREE->zn = k;
        TREE->left = TREE->right = NULL;
    }
 
    //2
    if (k < TREE->zn)
    {
        if (TREE->left != NULL) vstavka(TREE->left, k);
        else
        {
            TREE->left = new Bin_tree<T>;
            TREE->left->left = TREE->left->right = NULL;
            TREE->left->zn = k;
        }
 
    }
 
    //3
    if (k > TREE->zn)
    {
        if (TREE->right != NULL) vstavka(TREE->right, k);
        else
        {
            TREE->right = new Bin_tree<T>;
            TREE->right->right = TREE->right->left = NULL;
            TREE->right->zn = k;
        }
    }
}
 
 
template <typename T>
void print(Bin_tree<T>*& tree) {
    if (tree != NULL)
    {
 
        print(tree->left);// переходим в левое поддерево пока не дойдем до конца слева
        cout << tree->zn << " __ "; // печатаем с левого конца поддерева
        print(tree->right);
        cout << endl;
    }
 
}
 
// проверка пустоты
template <typename T>
void proverka(Bin_tree<T>* koren)
{
    if (koren == NULL)
        cout << " derevo pusto" << endl;
    else
        cout << "ne pustoe " << endl;
}
 
//удаление бин дерева
template <typename T>
void udal_derev(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        udal_derev(tree->left);
        udal_derev(tree->right);
        delete tree;
        tree = NULL;
    }
 
}
 
int main()
{
    setlocale(LC_ALL, "RUS");
    Bin_tree<int>* tree = NULL;
 
 
    int chislo;
    chislo = 10;
 
    while (chislo != 322)
    {
        cout << "Выберете операцию, осуществляемую с бинарным деревом:" << endl;
        cout << "1) вставка элементов в бинарное дерево поиска;\n"
            "2) удаление элемента из бинарного дерево поиска;\n"
            "3) поиск элемента в бинарном дереве поиска;\n"
            "4) обход бинарного дерева поиска(пкл);\n"
            "5) обход бинарного дерева поиска(клп);\n"
            "6) вывод бинарного дерева поиска;\n"
            "7) проверка пустоты дерева;\n"
            "8) удаление бинарного дерева поиска\n"
            "322) выйти из меню\n" << endl;
        cin >> chislo;
        if (chislo == 1)
        {
            int s;
            int n;
            cout << "kolvo elementov dobavlyemoe  v derevo: " << endl;
            cin >> n;
            for (int i = 0; i < n; ++i)
            {
                cin >> s;
                vstavka(tree, s);
            }
        }
        if (chislo == 2)
        {
            cout << "Введите элемент" << endl;
            int p;
            cin >> p;
            udal_elem(tree, p);
            cout << endl;
        }
        if (chislo == 3)
        {
            cout << "Введите элемент" << endl;
            int q;
            cin >> q;
            poisk(tree, q);
            cout << endl;
        }
        if (chislo == 4)
        {
            cout << "Обход бинарного дерева поиска(ПКЛ):" << endl;
            PKL(tree);
        }
        if (chislo == 5)
        {
            cout << "Обход бинарного дерева поиска(КЛП):" << endl;
            KLP(tree);
            cout << endl;
        }
        if (chislo == 6)
        {
            cout << "binarnoe derevo: " << endl;
            print(tree);
        }
        if (chislo == 7)
        {
            proverka(tree);
            cout << endl;
        }
        if (chislo == 8)
        {
            udal_derev(tree);
            cout << endl;
        }
 
    }
    int oo;
    cin >> oo;
    return 0;
}

@ibse · 28.09.2019, 13:09

Dedy111ka,

C++

#include <iostream>
using namespace std;
 
class konus
{
private:
    double rad_osn;
    double h;
public:
    konus() {};
    konus(double rad_, double h_)
    {
        rad_osn = rad_;
        h = h_;
    }
    double pl_kon()
    {
        return 3.14 * rad_osn * rad_osn + 3.14 * rad_osn * sqrt((rad_osn * rad_osn) + (h * h));
    }
 
    friend bool operator < (konus, konus);
    friend bool operator ==(konus, konus);
 
    friend ostream& operator <<(ostream&, konus);
    friend istream& operator >>(istream&, konus&);
 
};
 
bool operator < (konus obj1, konus obj2)
{
    return (obj1.pl_kon() < obj2.pl_kon());
}
bool operator ==(konus obj1, konus obj2)
{
    return (obj1.pl_kon() == obj2.pl_kon());
}
 
istream& operator >> (istream& is, konus& obj1)
{
    cout << "vvedite" << endl;
    is >> obj1.rad_osn >> obj1.h;
    return is;
}
ostream& operator << (ostream& os, konus obj)
{
    cout << "vivod" << endl;
    os << obj.rad_osn << obj.h;
    return os;
}
 
template <class T>
 
 
class Bin_tree
{
 
public:
    T zn;// число в дерево
    Bin_tree* left; // указатель на левый
    Bin_tree* right; // указатель на правый
};
 
 
template <typename T>
Bin_tree<T>* getmin(Bin_tree<T>* Tree, Bin_tree<T>*& prev)
{
    //static int k = 0;
    ////prev = Tree;
    //if (k == 2) return NULL;
    //k++;
    if (Tree == NULL)
    {
        return NULL;
    }
    if (Tree->left != NULL)
    {
        Bin_tree<T>* tmp =  getmin(Tree->left, Tree);
        prev = Tree;
        return tmp;
    }
    else
    {
        return Tree;
    }
}
 
//template <typename T>
//Bin_tree<T>* getmin(Bin_tree<T>*& Tree)
//{
//
//  if (Tree == NULL)
//  {
//      return NULL;
//  }
//  if (Tree->left != NULL)
//  {
//      getmin(Tree->left);
//  }
//  else
//  {
//      return Tree;
//  }
//}
 
// удаление элем
template <typename T>
void udal_elem(Bin_tree<T>* tree, T b, Bin_tree<T>* prev = NULL)
{
    if (tree != NULL)
    {
        if (b == tree->zn)
        {
            if ((tree->left == NULL) && (tree->right == NULL))
            {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = NULL;
                else
                    prev->left = NULL;
                delete tree;
            }
            else if (tree->left == NULL && tree->right != NULL)
            {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = tree->right;
                else
                    prev->left = tree->right;
                delete tree;
            }
            else if (tree->left != NULL && tree->right == NULL) {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = tree->left;
                else
                    prev->left = tree->left;
                delete tree;
 
            }
            else if (tree->left != NULL && tree->right != NULL)
            {
                Bin_tree<T>* prev = NULL;
                Bin_tree<T>* ptr = getmin(tree->right, prev);
                if (ptr->right == NULL) {
                    if (prev != NULL)
                        prev->left = NULL;
                }
                else {
                    if (prev != NULL)
                        prev->left = ptr->right;
                }
                tree->zn = ptr->zn;
                delete ptr;
            }
 
        }
        else if (b < tree->zn)  //   c помощью 1 и 2 if идем влево 
            //потом вправо пока не найдем нужный элемент и не вызовем рекурсивную функцию
        {
            udal_elem(tree->left, b, tree); // рекурсия 
        }
        else if (b > tree->zn)
        {
            udal_elem(tree->right, b, tree); // рекурсия
        }
    }
    else
    {
        cout << " elementa net " << endl;
    }
}
 
// поиск
template <typename T>
void poisk(Bin_tree<T>* Tree, T a)
{
    if (Tree != NULL)
    {
        if (Tree->zn == a)
        {
            cout << "Элемент найден" << endl;
            return;
        }
        else if (a < Tree->zn)
        {
            poisk(Tree->left, a);
        }
        else if (a > Tree->zn)
        {
            poisk(Tree->right, a);
        }
 
    }
    else
    {
        cout << "net elementa" << endl;
    }
}
 
// обход пкл
template <typename T>
void PKL(Bin_tree<T>* Tree)
{
    if (Tree != NULL)
    {
        PKL(Tree->right);
        cout << Tree->zn << "\t";
        PKL(Tree->left);
    }
}
 
// обход клп
template <typename T>
void KLP(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        cout << tree->zn << "\t";
        KLP(tree->left);
        KLP(tree->right);
    }
}
 
// вставка элемента
template <typename T>
void vstavka(Bin_tree<T>*& TREE, T k)
{
    //1
    if (TREE == NULL)
    {
        TREE = new Bin_tree<T>;
        TREE->zn = k;
        TREE->left = TREE->right = NULL;
    }
 
    //2
    if (k < TREE->zn)
    {
        if (TREE->left != NULL) vstavka(TREE->left, k);
        else
        {
            TREE->left = new Bin_tree<T>;
            TREE->left->left = TREE->left->right = NULL;
            TREE->left->zn = k;
        }
 
    }
 
    //3
    if (k > TREE->zn)
    {
        if (TREE->right != NULL) vstavka(TREE->right, k);
        else
        {
            TREE->right = new Bin_tree<T>;
            TREE->right->right = TREE->right->left = NULL;
            TREE->right->zn = k;
        }
    }
}
 
 
template <typename T>
void print(Bin_tree<T>*& tree) {
    if (tree != NULL)
    {
 
        print(tree->left);// переходим в левое поддерево пока не дойдем до конца слева
        cout << tree->zn << " __ "; // печатаем с левого конца поддерева
        print(tree->right);
        cout << endl;
    }
 
}
 
// проверка пустоты
template <typename T>
void proverka(Bin_tree<T>* koren)
{
    if (koren == NULL)
        cout << " derevo pusto" << endl;
    else
        cout << "ne pustoe " << endl;
}
 
//удаление бин дерева
template <typename T>
void udal_derev(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        udal_derev(tree->left);
        udal_derev(tree->right);
        delete tree;
        tree = NULL;
    }
 
}
 
void f(int*& c) {
    c = new int(8);
}
int main()
{
    //int* c = new int(7);
    //f(c);
    setlocale(LC_ALL, "RUS");
    Bin_tree<int>* tree = NULL;
 
 
    int chislo;
    chislo = 10;
 
    while (chislo != 322)
    {
        cout << "Выберете операцию, осуществляемую с бинарным деревом:" << endl;
        cout << "1) вставка элементов в бинарное дерево поиска;\n"
            "2) удаление элемента из бинарного дерево поиска;\n"
            "3) поиск элемента в бинарном дереве поиска;\n"
            "4) обход бинарного дерева поиска(пкл);\n"
            "5) обход бинарного дерева поиска(клп);\n"
            "6) вывод бинарного дерева поиска;\n"
            "7) проверка пустоты дерева;\n"
            "8) удаление бинарного дерева поиска\n"
            "322) выйти из меню\n" << endl;
        cin >> chislo;
        if (chislo == 1)
        {
            int s;
            int n;
            cout << "kolvo elementov dobavlyemoe  v derevo: " << endl;
            cin >> n;
            for (int i = 0; i < n; ++i)
            {
                cin >> s;
                vstavka(tree, s);
            }
        }
        if (chislo == 2)
        {
            cout << "Введите элемент" << endl;
            int p;
            cin >> p;
            udal_elem(tree, p);
            cout << endl;
        }
        if (chislo == 3)
        {
            cout << "Введите элемент" << endl;
            int q;
            cin >> q;
            poisk(tree, q);
            cout << endl;
        }
        if (chislo == 4)
        {
            cout << "Обход бинарного дерева поиска(ПКЛ):" << endl;
            PKL(tree);
        }
        if (chislo == 5)
        {
            cout << "Обход бинарного дерева поиска(КЛП):" << endl;
            KLP(tree);
            cout << endl;
        }
        if (chislo == 6)
        {
            cout << "binarnoe derevo: " << endl;
            print(tree);
        }
        if (chislo == 7)
        {
            proverka(tree);
            cout << endl;
        }
        if (chislo == 8)
        {
            udal_derev(tree);
            cout << endl;
        }
 
    }
    int oo;
    cin >> oo;
    return 0;
}

@Dedy111ka · 30.09.2019, 11:17 **[ТС]**

Не подскажете, как еще сделать нормальный вывод, чтобы было похоже на «дерево»

@kitsoRik · 30.09.2019, 11:54

Dedy111ka, нарисуй в пеинте как ты хочешь что бы это выглядело в консоле.

@Dedy111ka · 30.09.2019, 12:16 **[ТС]**

Так можно?

@ibse · 30.09.2019, 12:28

Dedy111ka, Дерево будет печататься, повернутое на 90◦ против часовой стрелки.

C++

#include <iostream>
using namespace std;
 
class konus
{
private:
    double rad_osn;
    double h;
public:
    konus() {};
    konus(double rad_, double h_)
    {
        rad_osn = rad_;
        h = h_;
    }
    double pl_kon()
    {
        return 3.14 * rad_osn * rad_osn + 3.14 * rad_osn * sqrt((rad_osn * rad_osn) + (h * h));
    }
 
    friend bool operator < (konus, konus);
    friend bool operator ==(konus, konus);
 
    friend ostream& operator <<(ostream&, konus);
    friend istream& operator >>(istream&, konus&);
 
};
 
bool operator < (konus obj1, konus obj2)
{
    return (obj1.pl_kon() < obj2.pl_kon());
}
bool operator ==(konus obj1, konus obj2)
{
    return (obj1.pl_kon() == obj2.pl_kon());
}
 
istream& operator >> (istream& is, konus& obj1)
{
    cout << "vvedite" << endl;
    is >> obj1.rad_osn >> obj1.h;
    return is;
}
ostream& operator << (ostream& os, konus obj)
{
    cout << "vivod" << endl;
    os << obj.rad_osn << obj.h;
    return os;
}
 
template <class T>
 
 
class Bin_tree
{
 
public:
    T zn;// число в дерево
    Bin_tree* left; // указатель на левый
    Bin_tree* right; // указатель на правый
};
 
 
template <typename T>
Bin_tree<T>* getmin(Bin_tree<T>* Tree, Bin_tree<T>*& prev)
{
    //static int k = 0;
    ////prev = Tree;
    //if (k == 2) return NULL;
    //k++;
    if (Tree == NULL)
    {
        return NULL;
    }
    if (Tree->left != NULL)
    {
        Bin_tree<T>* tmp = getmin(Tree->left, Tree);
        prev = Tree;
        return tmp;
    }
    else
    {
        return Tree;
    }
}
 
//template <typename T>
//Bin_tree<T>* getmin(Bin_tree<T>*& Tree)
//{
//
//  if (Tree == NULL)
//  {
//      return NULL;
//  }
//  if (Tree->left != NULL)
//  {
//      getmin(Tree->left);
//  }
//  else
//  {
//      return Tree;
//  }
//}
 
// удаление элем
template <typename T>
void udal_elem(Bin_tree<T>* tree, T b, Bin_tree<T>* prev = NULL)
{
    if (tree != NULL)
    {
        if (b == tree->zn)
        {
            if ((tree->left == NULL) && (tree->right == NULL))
            {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = NULL;
                else
                    prev->left = NULL;
                delete tree;
            }
            else if (tree->left == NULL && tree->right != NULL)
            {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = tree->right;
                else
                    prev->left = tree->right;
                delete tree;
            }
            else if (tree->left != NULL && tree->right == NULL) {
                if (prev != NULL && prev->zn <= tree->zn)
                    prev->right = tree->left;
                else
                    prev->left = tree->left;
                delete tree;
 
            }
            else if (tree->left != NULL && tree->right != NULL)
            {
                Bin_tree<T>* prev = NULL;
                Bin_tree<T>* ptr = getmin(tree->right, prev);
                if (ptr->right == NULL) {
                    if (prev != NULL)
                        prev->left = NULL;
                }
                else {
                    if (prev != NULL)
                        prev->left = ptr->right;
                }
                tree->zn = ptr->zn;
                delete ptr;
            }
 
        }
        else if (b < tree->zn)  //   c помощью 1 и 2 if идем влево 
            //потом вправо пока не найдем нужный элемент и не вызовем рекурсивную функцию
        {
            udal_elem(tree->left, b, tree); // рекурсия 
        }
        else if (b > tree->zn)
        {
            udal_elem(tree->right, b, tree); // рекурсия
        }
    }
    else
    {
        cout << " elementa net " << endl;
    }
}
 
// поиск
template <typename T>
void poisk(Bin_tree<T>* Tree, T a)
{
    if (Tree != NULL)
    {
        if (Tree->zn == a)
        {
            cout << "Элемент найден" << endl;
            return;
        }
        else if (a < Tree->zn)
        {
            poisk(Tree->left, a);
        }
        else if (a > Tree->zn)
        {
            poisk(Tree->right, a);
        }
 
    }
    else
    {
        cout << "net elementa" << endl;
    }
}
 
// обход пкл
template <typename T>
void PKL(Bin_tree<T>* Tree)
{
    if (Tree != NULL)
    {
        PKL(Tree->right);
        cout << Tree->zn << "\t";
        PKL(Tree->left);
    }
}
 
// обход клп
template <typename T>
void KLP(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        cout << tree->zn << "\t";
        KLP(tree->left);
        KLP(tree->right);
    }
}
 
// вставка элемента
template <typename T>
void vstavka(Bin_tree<T>*& TREE, T k)
{
    //1
    if (TREE == NULL)
    {
        TREE = new Bin_tree<T>;
        TREE->zn = k;
        TREE->left = TREE->right = NULL;
    }
 
    //2
    if (k < TREE->zn)
    {
        if (TREE->left != NULL) vstavka(TREE->left, k);
        else
        {
            TREE->left = new Bin_tree<T>;
            TREE->left->left = TREE->left->right = NULL;
            TREE->left->zn = k;
        }
 
    }
 
    //3
    if (k > TREE->zn)
    {
        if (TREE->right != NULL) vstavka(TREE->right, k);
        else
        {
            TREE->right = new Bin_tree<T>;
            TREE->right->right = TREE->right->left = NULL;
            TREE->right->zn = k;
        }
    }
}
 
 
template <class T>
void print(Bin_tree<T>* r, int offset = 0)
{
    if (r == nullptr) return;
    print(r->right, offset + 3);
    for (int i = 0; i < offset; i++)
        cout << " ";
    cout << r->zn << endl;
    print(r->left, offset + 3);
}
 
// проверка пустоты
template <typename T>
void proverka(Bin_tree<T>* koren)
{
    if (koren == NULL)
        cout << " derevo pusto" << endl;
    else
        cout << "ne pustoe " << endl;
}
 
//удаление бин дерева
template <typename T>
void udal_derev(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        udal_derev(tree->left);
        udal_derev(tree->right);
        delete tree;
        tree = NULL;
    }
 
}
 
void f(int*& c) {
    c = new int(8);
}
int main()
{
    //int* c = new int(7);
    //f(c);
    setlocale(LC_ALL, "RUS");
    Bin_tree<int>* tree = NULL;
 
 
    int chislo;
    chislo = 10;
 
    while (chislo != 322)
    {
        cout << "Выберете операцию, осуществляемую с бинарным деревом:" << endl;
        cout << "1) вставка элементов в бинарное дерево поиска;\n"
            "2) удаление элемента из бинарного дерево поиска;\n"
            "3) поиск элемента в бинарном дереве поиска;\n"
            "4) обход бинарного дерева поиска(пкл);\n"
            "5) обход бинарного дерева поиска(клп);\n"
            "6) вывод бинарного дерева поиска;\n"
            "7) проверка пустоты дерева;\n"
            "8) удаление бинарного дерева поиска\n"
            "322) выйти из меню\n" << endl;
        cin >> chislo;
        if (chislo == 1)
        {
            int s;
            int n;
            cout << "kolvo elementov dobavlyemoe  v derevo: " << endl;
            cin >> n;
            for (int i = 0; i < n; ++i)
            {
                cin >> s;
                vstavka(tree, s);
            }
        }
        if (chislo == 2)
        {
            cout << "Введите элемент" << endl;
            int p;
            cin >> p;
            udal_elem(tree, p);
            cout << endl;
        }
        if (chislo == 3)
        {
            cout << "Введите элемент" << endl;
            int q;
            cin >> q;
            poisk(tree, q);
            cout << endl;
        }
        if (chislo == 4)
        {
            cout << "Обход бинарного дерева поиска(ПКЛ):" << endl;
            PKL(tree);
        }
        if (chislo == 5)
        {
            cout << "Обход бинарного дерева поиска(КЛП):" << endl;
            KLP(tree);
            cout << endl;
        }
        if (chislo == 6)
        {
            cout << "binarnoe derevo: " << endl;
            print(tree);
        }
        if (chislo == 7)
        {
            proverka(tree);
            cout << endl;
        }
        if (chislo == 8)
        {
            udal_derev(tree);
            cout << endl;
        }
 
    }
    int oo;
    cin >> oo;
    return 0;
}

@Dedy111ka · 18.10.2019, 19:48 **[ТС]**

ibse, а как сделать так, чтобы работала и для созданного класса? А то у меня только для int работает

IGPIGP · 18.10.2019, 19:56

Dedy111ka,

Сообщение от Dedy111ka

if (Tree->zn == a)

для целых чисел это не проблема, а для вашего класса - вопрос. Так же могу быть проблемы и с другими операциями. Например с присваиванием. И конструктора нужны могут быть (умолч./копир.). Посмотрите и сделайте. Компилятор об этом должен намекнуть, хотя он не навязчив и не всегда говорит прямо.

@Dedy111ka · 18.10.2019, 19:59 **[ТС]**

IGPIGP, если класс другой, например, дробь, у которой целочисленные числитель и знаменатель, критерий сравнения-сумма квадратов числителя и знаменателя

IGPIGP · 18.10.2019, 20:01

Сообщение от Dedy111ka

IGPIGP, если класс другой, например, дробь, у которой целочисленные числитель и знаменатель, критерий сравнения-сумма квадратов числителя и знаменателя

оператор сравнения < тоже оператор. Он едва ли не самый важный в штабеле операторов, которые придётся перегружать. Собственноручно, причём.

@Dedy111ka · 18.10.2019, 20:02 **[ТС]**

IGPIGP,

C++

#include <iostream>
using namespace std;
 
class drob
{
private:
    int chislitel;
    int znamenatel;
public:
    drob() {};
    drob(int chislitel_, int znamenatel_)
    {
        chislitel = chislitel_;
        znamenatel = znamenatel_;
    }
    int summa_kv()
    {
        return chislitel * chislitel + znamenatel * znamenatel;
    }
 
    friend bool operator < (drob, drob);
    friend bool operator ==(drob, drob);
 
    friend ostream& operator <<(ostream&, drob);
    friend istream& operator >>(istream&, drob&);
 
};
 
bool operator < (drob obj1, drob obj2)
{
    return (obj1.summa_kv() < obj2.summa_kv());
}
bool operator ==(drob obj1, drob obj2)
{
    return (obj1.summa_kv() == obj2.summa_kv());
}
 
istream& operator >> (istream& is, drob& obj1)
{
    cout << "Введите: " << endl;
    is >> obj1.chislitel >> obj1.znamenatel;
    return is;
}
ostream& operator << (ostream& os, drob obj)
{
    cout << "Вывод " << endl;
    os << obj.chislitel << obj.znamenatel;
    return os;
}
 
 
template <class T>
 
 
class Bin_tree
{
 
public:
    T zn;// число в дерево
    Bin_tree* left; // указатель на левый
    Bin_tree* right; // указатель на правый
};
 
// поиск минимального
template <typename T>
Bin_tree<T>* getmin(Bin_tree<T>*& Tree)
{
 
    if (Tree == NULL)
    {
        return NULL;
    }
    if (Tree->left != NULL)
    {
        getmin(Tree->left);
    }
    else
    {
        return Tree;
    }
}
 
// удаление элем
template <typename T>
void udal_elem(Bin_tree<T>*& tree, T b)
{
    if (tree != NULL)
    {
        if (b == tree->zn)
        {
            if ((tree->left == NULL) && (tree->right == NULL))
            {
                delete tree;
                tree = NULL;
 
            }
            else if (tree->left == NULL && tree->right != NULL)
            {
 
                tree = tree->right;
                tree->right = NULL;
 
            }
            else if (tree->left != NULL && tree->right == NULL) {
                tree = tree->left;
                tree->left = NULL;
 
            }
            else if (tree->left != NULL && tree->right != NULL)
            {
                Bin_tree<T>* ptr = getmin(tree->right);
                tree->zn = ptr->zn;
                udal_elem(tree->right, ptr->zn);
 
            }
 
        }
        else if (b < tree->zn)  //   c помощью 1 и 2 if идем влево 
                                //потом вправо пока не найдем нужный элемент и не вызовем рекурсивную функцию
        {
            udal_elem(tree->left, b); // рекурсия 
        }
        else if (b > tree->zn)
        {
            udal_elem(tree->right, b); // рекурсия
        }
    }
    else
    {
        cout << "Элемента нет " << endl;
    }
}
 
// поиск
template <typename T>
void poisk(Bin_tree<T>* Tree, T a)
{
    if (Tree != NULL)
    {
        if (Tree->zn == a)
        {
            cout << "Элемент найден" << endl;
            return;
        }
        else if (a < Tree->zn)
        {
            poisk(Tree->left, a);
        }
        else if (a > Tree->zn)
        {
            poisk(Tree->right, a);
        }
 
    }
    else
    {
        cout << "Нет элемента " << endl;
    }
}
 
// обход пкл
template <typename T>
void PKL(Bin_tree<T>* Tree)
{
    if (Tree != NULL)
    {
        PKL(Tree->right);
        cout << Tree->zn << "\t";
        PKL(Tree->left);
    }
    else return;
}
 
// обход лпk
template <typename T>
void LPK(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        LPK(tree->left);
        LPK(tree->right);
        cout << tree->zn << "\t";
    }
}
 
// вставка элемента
template <typename T>
void vstavka(Bin_tree<T>*& TREE, T k)
{
    //1
    if (TREE == NULL)
    {
        TREE = new Bin_tree<T>;
        TREE->zn = k;
        TREE->left = TREE->right = NULL;
    }
 
    //2
    if (k < TREE->zn)
    {
        if (TREE->left != NULL) vstavka(TREE->left, k);
        else
        {
            TREE->left = new Bin_tree<T>;
            TREE->left->left = TREE->left->right = NULL;
            TREE->left->zn = k;
        }
 
    }
 
    //3
    if (k > TREE->zn)
    {
        if (TREE->right != NULL) vstavka(TREE->right, k);
        else
        {
            TREE->right = new Bin_tree<T>;
            TREE->right->right = TREE->right->left = NULL;
            TREE->right->zn = k;
        }
    }
}
 
 
template <typename T>
void print(Bin_tree<T>*& tree, int n) {
    if (tree != NULL)
    {
        print(tree->right, n + 1);// переходим в правое поддерево пока не дойдем до конца справа, n+1-счетчик и одновременно считает колво справа 
        for (int i = 0; i < n; i++)
        {
            cout << "   "; // на i-ом проходе делаем tabуляцию
        }
        cout << tree->zn << endl; // начинаем справа
        print(tree->left, n + 1);
 
    }
 
}
 
// проверка пустоты
template <typename T>
void proverka(Bin_tree<T>* koren)
{
    if (koren == NULL)
        cout << "Дерево пусто " << endl;
    else
        cout << "Не пустое " << endl;
}
 
//удаление бин дерева
template <typename T>
void udal_derev(Bin_tree<T>* tree)
{
    if (tree != NULL)
    {
        udal_derev(tree->left);
        udal_derev(tree->right);
        delete tree;
        tree = NULL;
    }
 
}
 
 
int main()
{
    setlocale(LC_ALL, "RUS");
    Bin_tree<int>* tree = NULL;
 
 
    int chislo;
    chislo = 10;
 
    while (chislo != 123)
    {
        cout << "Выберете операцию, осуществляемую с бинарным деревом:" << endl;
        cout << "1) вставка элементов в бинарное дерево поиска;\n"
            "2) удаление элемента из бинарного дерево поиска;\n"
            "3) поиск элемента в бинарном дереве поиска;\n"
            "4) обход бинарного дерева поиска(пкл);\n"
            "5) обход бинарного дерева поиска(лпk);\n"
            "6) вывод бинарного дерева поиска;\n"
            "7) проверка пустоты дерева;\n"
            "8) удаление бинарного дерева поиска\n"
            "123) выйти из меню\n" << endl;
        cin >> chislo;
        if (chislo == 1)
        {
            int s;
            int n;
            cout << "Количество элементов, добавляемых в дерево: " << endl;
            cin >> n;
            for (int i = 0; i < n; ++i)
            {
                cin >> s;
                vstavka(tree, s);
            }
        }
        if (chislo == 2)
        {
            cout << "Введите элемент " << endl;
            int p;
            cin >> p;
            udal_elem(tree, p);
            cout << endl;
        }
        if (chislo == 3)
        {
            cout << "Введите элемент " << endl;
            int q;
            cin >> q;
            poisk(tree, q);
            cout << endl;
        }
        if (chislo == 4)
        {
            cout << "Обход бинарного дерева поиска(ПКЛ): " << endl;
            PKL(tree);
        }
        if (chislo == 5)
        {
            cout << "Обход бинарного дерева поиска(ЛПK): " << endl;
            LPK(tree);
            cout << endl;
        }
        if (chislo == 6)
        {
            cout << "Бинарное дерево: " << endl;
            print(tree, 0);
        }
        if (chislo == 7)
        {
            proverka(tree);
            cout << endl;
        }
        if (chislo == 8)
        {
            udal_derev(tree);
            cout << endl;
        }
 
    }
    cin.get();
    return 0;
}

IGPIGP · 18.10.2019, 20:05

Сообщение от Dedy111ka

IGPIGP,

Хотите сподвигнуть меня к компиляции? Я пока не расположен. Напишите (дословно), или скопируйте, сообщения компилятора и покажите код который пытается это дерево потрясти... или окучить.

@Dedy111ka · 18.10.2019, 20:06 **[ТС]**

программа рабочая, я просто не знаю, как мне класс в дерево засунуть

IGPIGP · 18.10.2019, 20:11

Сообщение от Dedy111ka

не знаю, как мне класс в дерево засунуть

У вас в дереве есть дупло. Оно шаблонное. То есть, ~~инстанцирование~~ , запихивание в дупло, состоит в том чтобы написать что-то вроде:

C++

1	Bin_tree<drob>my_drob_tree;

То есть, стряляйте дробью в створ дупла обозначенный двумя угловыми скобками <>. Промахнуться трудно. Задержите дыхание, прицельтесь... и бах!
Потом пушьте, инсёртте или как там вы предусмотрели его заполнять...

@Dedy111ka 0 / 0 / 0 Регистрация: 20.02.2019 Сообщений: 131
	30.09.2019, 11:17 [ТС]	3
	Не подскажете, как еще сделать нормальный вывод, чтобы было похоже на «дерево» 0

@kitsoRik 490 / 286 / 129 Регистрация: 30.10.2018 Сообщений: 1,309
	30.09.2019, 11:54	4
	Dedy111ka, нарисуй в пеинте как ты хочешь что бы это выглядело в консоле. 0

@Dedy111ka 0 / 0 / 0 Регистрация: 20.02.2019 Сообщений: 131
	30.09.2019, 12:16 [ТС]	5
	Так можно? Миниатюры 0

@Dedy111ka 0 / 0 / 0 Регистрация: 20.02.2019 Сообщений: 131
	18.10.2019, 19:48 [ТС]	7
	ibse, а как сделать так, чтобы работала и для созданного класса? А то у меня только для int работает 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8916 / 4677 / 626 Регистрация: 04.12.2011 Сообщений: 13,912 Записей в блоге: 16
	18.10.2019, 19:56	8
	Dedy111ka, Сообщение от Dedy111ka if (Tree->zn == a) для целых чисел это не проблема, а для вашего класса - вопрос. Так же могу быть проблемы и с другими операциями. Например с присваиванием. И конструктора нужны могут быть (умолч./копир.). Посмотрите и сделайте. Компилятор об этом должен намекнуть, хотя он не навязчив и не всегда говорит прямо. 0

@Dedy111ka 0 / 0 / 0 Регистрация: 20.02.2019 Сообщений: 131
	18.10.2019, 19:59 [ТС]	9
	IGPIGP, если класс другой, например, дробь, у которой целочисленные числитель и знаменатель, критерий сравнения-сумма квадратов числителя и знаменателя 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8916 / 4677 / 626 Регистрация: 04.12.2011 Сообщений: 13,912 Записей в блоге: 16
	18.10.2019, 20:01	10
	Сообщение от Dedy111ka IGPIGP, если класс другой, например, дробь, у которой целочисленные числитель и знаменатель, критерий сравнения-сумма квадратов числителя и знаменателя оператор сравнения < тоже оператор. Он едва ли не самый важный в штабеле операторов, которые придётся перегружать. Собственноручно, причём. 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8916 / 4677 / 626 Регистрация: 04.12.2011 Сообщений: 13,912 Записей в блоге: 16
	18.10.2019, 20:05	12
	Сообщение от Dedy111ka IGPIGP, Хотите сподвигнуть меня к компиляции? Я пока не расположен. Напишите (дословно), или скопируйте, сообщения компилятора и покажите код который пытается это дерево потрясти... или окучить. 0

@Dedy111ka 0 / 0 / 0 Регистрация: 20.02.2019 Сообщений: 131
	18.10.2019, 20:06 [ТС]	13
	программа рабочая, я просто не знаю, как мне класс в дерево засунуть 0

Опции темы