С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.53/40: Рейтинг темы: голосов - 40, средняя оценка - 4.53
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
1

Удаление элементов из бинарного дерева

28.11.2017, 09:49. Показов 7946. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доброго времени суток!
Реализую обычное бинарное дерево (НЕ поиска) на базе массива (то еще извращение ._.)
Следует написать функцию удаление элемента. Если элемент имеет дочерние узлы, то удаляется всё поддерево.

Написала часть функции, а именно: случай с удалением листа и случай с одним дочерним узлом.
Что делать, если узел имеет два дочерних узла - ума не приложу. Еще страшнее кажется ситуация, если дочерние узлы тоже имеют своих потомков
Подозреваю, что функцию придется вызывать рекурсивно, но это мало что дает

Заранее благодарю.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <math.h>
 
#define N 20 //максимальная длина массива
 
using namespace std;
 
class tree {
    int bin[N];       //сам массив
    int size;         //текущая длина массива
public:
    tree(int n);         //конструктор
    int child(int i);         //функция определения количества потомков
    void insert(int value);           //вставка элемента
    void show();                        //вывод элементов
    int find(int v);                    //поиск элемента
    void del(int v);            //удаление элемента
};
 
tree::tree(int n) {
    if (n>=N) {
        for (int i=0; i<N; ++i)
            bin[i]=i+1;
        cout << "Sozdano derevo iz " << N << " elementov.\n"; 
        size=N;
    } else {
        for (int i=0; i<n; ++i)
            bin[i]=i+1; 
        cout << "Sozdano derevo iz " << n << " elementov.\n";
        size=n; 
    }
}
 
void tree::del(int v) {
    int x=find(v);
    if (x>=0) {                                                                 //если элемент найден, то смотрим, сколько у него потомков
        if (child(x)==-1) {
            for (int i=x; i<size; ++i)                               //если ни одного, то просто удаляем элемент и уменьшаем массив
                bin[i]=bin[i+1];
            size--;
            return;
        } else if (child(x)==1) {                //если один, то перезаписываем элемент, уменьшаем массив и повторяем функцию
            int c=(x+1)*2-1;
            bin[x]=bin[c];
            size--;
            del(bin[x]);
        } else if (child(x)==2) {                //если два, то ...
            // помогите
        }
    } else {
        cout << "\nUzla net.";
        return;
    }
}
 
int tree::find(int v) {
    for (int i=0; i<size; ++i)
        if (bin[i]==v) return i;
}
 
void tree::show() {
    for (int i=0; i<size; ++i) {
        for (int k=0; k<5; ++k) {
            if (i==pow(2,k)-1) cout << endl;
        }
        cout << " " << bin[i] << " ";
    }   
}
 
void tree::insert(int value) {
    if (size==N) {
        cout << "\nDerevo zapolneno.";
        return;
    } else {
        size++;
        bin[size-1]=value;
    }   
}
 
int tree::child(int i) {
    int j=i;
    if ((j+1)*2 <= size-1) {
        cout << "\nUzel imeet 2 child: " << bin[(j+1)*2-1] << " " << bin[(j+1)*2];
        return 2;
    } else if (((j+1)*2-1 <= size-1)&&((j+1)*2 > size-1)) {
        cout << "\nUzel imeet 1 child: " << bin[(j+1)*2-1];
        return 1;
    } else {
        cout << "\nUzel ne imeet child.";
        return -1; 
    }
}
 
int main(int argc, char** argv) {
    tree a(10);
    a.child(5);
    a.insert(11);
    a.child(5);
    cout << endl; a.show();
    a.del(7);
    cout << endl; a.show();
    a.del(5);
    cout << endl; a.show(); 
    a.insert(20); a.insert(30);
    cout << endl; a.show(); 
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.11.2017, 09:49
Ответы с готовыми решениями:

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

Удаление элементов из бинарного дерева (не дерево поиска)
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении...

Удаление из бинарного дерева
Здравствуйте! Помогите с удалением узла из бинарного дерева. Номер узла вводится пользователем ...

Удаление Узла бинарного дерева
Добрый вечер. Имеем Бинарное дерево поиска. При удалении некоторого узла . возникают три...

16
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
28.11.2017, 10:00 2
Лучший ответ Сообщение было отмечено Okozaoko как решение

Решение

Либо рекурсия, либо через контейнер.
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
28.11.2017, 10:02  [ТС] 3
И как это реализовать? У Вас есть какие-нибудь конкретные примеры?
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
28.11.2017, 10:24 4
Если дерево в массиве, то при удалении в элемент записывается специальное значение. Не вижу у тебя такого.
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
28.11.2017, 10:39  [ТС] 5
Конечно, не видите, ведь я даже не до конца понимаю, что Вы имеете в виду
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
28.11.2017, 10:46 6
Дерево всегда хранится как полное, если каких-то узлов нет, то в ячейку записывают специальное значение. Никаких сдвигов элементов не делают. Нужно просто пометить удаляемый узел и его потомков. А координаты вычисляются по формулам.
Здесь смотри "Представление бинарного дерева в виде массива": http://mirznanii.com/a/314244/... de-massiva
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
28.11.2017, 11:07  [ТС] 7
Хорошо, я прочитала и поняла. Но нам просто иначе всё объясняли. И формулы узлов у нас другие (левый: 2*(i+1)-1, правый: 2*(i+1)).
Чувствую, если я сделаю по данному примеру, то ничего хорошего из этого не выйдет
Миниатюры
Удаление элементов из бинарного дерева  
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
28.11.2017, 13:36 8
Цитата Сообщение от Okozaoko Посмотреть сообщение
формулы узлов у нас другие
А где k?
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
01.12.2017, 12:21  [ТС] 9
Я Вам еще раз повторяю: у нас совершенно другие формулы, совершенно другой подход
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
01.12.2017, 12:23 10
Может, у вас и математика другая? И физика тоже.
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
01.12.2017, 12:43  [ТС] 11
Может быть, но это сути не меняет
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
07.12.2017, 11:14  [ТС] 12
Задача решена.
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
07.12.2017, 12:19 13
Кем?
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
07.12.2017, 12:23  [ТС] 14
Мной, кем же ещё?
Посидела и поразмыслила: при удалении элемента, у которого два дочерних узла, в массиве реализовать невозможно. По той простой причине, что нужно будет каждый раз смещать элемента массива, что приведет к потере дочерних узлов и одних элементов и перезапись - у других.
Объяснила на примерах преподавателю, со мной согласились.
Функцию решили реализовать так: если у удаляемого узла два потомка, то на место удаляемого записываем самый последний элемент массива.
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
07.12.2017, 12:26 15

Не по теме:

Цитата Сообщение от Okozaoko Посмотреть сообщение
Мной, кем же ещё?
:D Да ладно, ты же девочка.


Цитата Сообщение от Okozaoko Посмотреть сообщение
По той простой причине, что нужно будет каждый раз смещать элемента массива
Я тебе уже писал, что такое дерево хранится в массиве как полное, никакого смещения не делают. Если какого-то узла нет, то в ячейку записывают спец. значение.
0
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
07.12.2017, 12:28  [ТС] 16
Цитата Сообщение от nmcf Посмотреть сообщение
такое дерево хранится в массиве как полное
Это один из подходов к реализации дерева на базе массива, но он же не единственный.

Цитата Сообщение от nmcf Посмотреть сообщение
ты же девочка.
Девушки не могут программировать?
0
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
07.12.2017, 12:32 17
Цитата Сообщение от Okozaoko Посмотреть сообщение
но он же не единственный
Для простого массива единственный. Ну можно усложнить элемент. Тогда получится по сути список в массиве - проще на указатели перейти.

Не по теме:

Цитата Сообщение от Okozaoko Посмотреть сообщение
Девушки не могут программировать?
Я в этом сомневаюсь. Лично не знаю таких.

0
07.12.2017, 12:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.12.2017, 12:32
Помогаю со студенческими работами здесь

Удаление элемента из бинарного дерева
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте,...

Удаление узла бинарного дерева
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени...

Удаление узла из бинарного дерева
всем доброго времени суток! имеется бинарное дерево, которое хранит в себе элементы с данными в...

Удаление вершины бинарного дерева
Как удалять вершины бинарного дерева вместе с потомками?

удаление элемента бинарного дерева
как удалить элемент бинарного дерева,имеющий 2 потомка?(например дерево (2)-(7 и 0)-(4 и...

Удаление узла из бинарного дерева
всем доброго времени суток. помогите пожалуйста с удалением элемента из дерево, а именно с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru