Бинарное дерево: удаление элементов

@Avgust · Регистрация: 03.11.2014

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

Помогите пожалуйста реализовать удаление элементов бинарного дерево, добавление и вывод вроде сделал, а тут путаюсь
Бинарное дерево реализовано так, что у каждого элемента 2 потомка, левый меньше либо равен предку, а правый больше
Тяжело просто сдвигать элементы вверх, если например удаляется предок, и при этом нужно его правый потомок поставить на место этого предка. в общем вот код, если нужно, помогите пожалуйста с удалением)

C++

# include <iostream>
using namespace std;
struct node{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
void push(int a, node **t){
    if ((*t) == NULL) //Если дерева не существует
    {
        (*t) = new node; //Выделяем память
        (*t)->info = a; //Кладем в выделенное место аргумент a
        (*t)->l = (*t)->r = NULL; // его левый и правый потомки присваиваем 0
        return;
    }
    //Дерево есть
    if (a>(*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    else push(a, &(*t)->l); //Иначе кладем его влево
}
void print(node *t, int u){
    if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
        print(t->l, ++u);//С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i<u; ++i) cout << "|"; // "выбираем крайний элемент и считаем сколько до него узлов"
        cout << t->info << endl; //И показываем элемент
        u--;
    }
    print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево
}
int main(){
    setlocale(0, "RUS");
    node * tree = NULL; //Объявляем переменную, тип которой структура Дерево
    char count;
    int n,s;
    do
    {
        cout << "1. Добавить элемент в дерево\n";
        cout << "2. Вывести дерево\n";
        cout << "0. Выйти\n";
        cin >> count;
        switch (count)
        {
        case '1':
            cout << "введите количество элементов  ";
            cin >> n; //Вводим количество элементов
 
            for (int i = 0; i<n; ++i)
            {
                cout << "ведите число  ";
                cin >> s; //Считываем элемент за элементом
 
                push(s, &tree); //И каждый кладем в дерево
            }
            break;
        case '2':
            print(tree, 0);
            break;
        case '3': break;
        default: cout << "Неверное значение, введите заново\n";
            break;
        }
    } while (count != '0');
    system("Pause");
    return 0;
}

@idm · 25.05.2015, 08:46

Оформите код читабельным образом, так Вам быстрее помогут.

Добавлено через 2 часа 24 минуты
Можно использовать рекурсивную функцию для удаления элементов.
Мы не можем просто присвоить NULL отцу так как навсегда потеряем доступ к памяти выделенной под потомков.
Алгоритм прост:
Удаляя элемент мы идем сначала например налево, смотрим если там не NULL, значит снова идем налево, если там NULL то идем на право, если там тоже NULL то удаляем, так как мы успешно проверили потомка на потомков то удаляем его и по рекурсии поднимаемся обратно наверх, где мы первый раз пошли налево и идем на право, если там не NULL то повторяем алгоритм для правого, если NULL то смело удаляем. Таким образом мы освободим всю выделенную память под отца и потомков успешно удалив элемент.
Так же рекомендую хранить в структуре данные об отце, заметно облегчит задачу.
И еще

Кликните здесь для просмотра всего текста

Написав new сразу пишите delete

@Avgust · 26.05.2015, 13:44 **[ТС]**

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

C++

# include <iostream>
 
using namespace std;
 
 
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
 
 
 
void push(int a, node **t)
{
    if ((*t) == NULL) //Если дерева не существует
    {
        (*t) = new node; //Выделяем память
        (*t)->info = a; //Кладем в выделенное место аргумент a
        (*t)->l = (*t)->r = NULL; // его левый и правый потомки присваиваем 0
        return;
    }
    //Дерево есть
    if (a>(*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    else push(a, &(*t)->l); //Иначе кладем его влево
}
 
 
void print(node *t, int u)
{
    if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
        print(t->l, ++u);//С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i<u; ++i) cout << "|"; // "выбираем крайний элемент и считаем сколько до него узлов"
        cout << t->info << endl; //И показываем элемент
        u--;
    }
    print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево
}
 
void find(node *t, int key)
{
    if (t == NULL) cout << "Элемент не найден\n";
    else {
        if (t->info == key) cout << "Элемент найден  " << key << "\n";
        else if (t->info > key) find(t->l, key);
        else if (t->info < key) find(t->r, key);
    }
}
 
void del(node *t, int key)
{
    if (t == NULL) return;
    if (t->info == key)
        delete t;
    else if (t->info > key)
        del(t->l, key);
    else if (t->info < key)
        del(t->r, key);
}
 
int main()
{
    setlocale(0, "RUS");
    node * tree = NULL; //Объявляем переменную, тип которой структура Дерево
    char count;
    int n,s;
    do
    {
        cout << "1. Добавить элемент в дерево\n";
        cout << "2. Вывести дерево\n";
        cout << "3. Найти элемент\n";
        cout << "0. Выйти\n";
        cin >> count;
        switch (count)
        {
        case '1':
            cout << "введите количество элементов  ";
            cin >> n;
 
            for (int i = 0; i<n; ++i)
            {
                cout << "ведите число  ";
                cin >> s;
 
                push(s, &tree);
            }
            break;
        case '2':
            print(tree, 0);
            break;
        case '3':
            cout << "Введите элемент, который хотите найти\n";
            int whattofind;
            cin >> whattofind;
            find(tree, whattofind);
            break;
        case '4':
            int whattodel;
            cin >> whattodel;
            del(tree, whattodel);
            break;
        case '0': break;
        default: cout << "Неверное значение, введите заново\n";
            break;
        }
    } while (count != '0');
    system("Pause");
    return 0;
}

@idm 120 / 34 / 19 Регистрация: 19.03.2015 Сообщений: 90
	25.05.2015, 08:46	2
	Оформите код читабельным образом, так Вам быстрее помогут. Добавлено через 2 часа 24 минуты Можно использовать рекурсивную функцию для удаления элементов. Мы не можем просто присвоить NULL отцу так как навсегда потеряем доступ к памяти выделенной под потомков. Алгоритм прост: Удаляя элемент мы идем сначала например налево, смотрим если там не NULL, значит снова идем налево, если там NULL то идем на право, если там тоже NULL то удаляем, так как мы успешно проверили потомка на потомков то удаляем его и по рекурсии поднимаемся обратно наверх, где мы первый раз пошли налево и идем на право, если там не NULL то повторяем алгоритм для правого, если NULL то смело удаляем. Таким образом мы освободим всю выделенную память под отца и потомков успешно удалив элемент. Так же рекомендую хранить в структуре данные об отце, заметно облегчит задачу. И еще Кликните здесь для просмотра всего текста Написав new сразу пишите delete 0

Опции темы