Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
#1

Удаление вершины дерева поиска - C++

30.06.2012, 12:08. Просмотров 1197. Ответов 7
Метки нет (Все метки)

Здравствуйте.
Не получается написать удаление вершины из дерева поиска, что бы после удаления, дерево оставалось деревом поиска.
Помогите пожалуйста реализовать. Все остальное написал.
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
 
//------------------------------------------------------------------------------------------------------------------------- 
struct  bin_tree
{
   int value;
   bin_tree *left, *right, *parent;
}
 
*pHead = NULL; // указатель на вершину равен нулю
 
//------------------------------------------------------------------------------------------------------------------------- 
 
int info, item;
 
void add_node(bin_tree*, int);   // добавление конкретного узла дерева
 
void add_bin_tree(int);    // проверка на "пустоту" дерева, если указатель на вершину равен нулю, создает узел
 
// обход
void printtree(bin_tree*, int Length);   // вывод дерева на экран
void obhod(bin_tree*, ofstream&);
 
//-----------------------------------------------------------------------------------------------------------------------
int main()
{
    setlocale (LC_ALL, "Russian");
    
    int el, ch;
    
    bool exit = false;
    
    ofstream fail("binTree.txt");  // эл-ты записываются в этот файл
    
    while (exit == false) // меню программы
    {
        printf("---------------------------------------------------------------------\n");
        printf("1) Введите последовательность\n");
        printf("2) Вывод дерева на экран\n");
        printf("3) Удаление эл-та из дерева\n");
        printf("4) Выход\n");
        printf("---------------------------------------------------------------------\n");
        
        ch=getch();
            switch(ch)
            {
                case '1':
                    cout << "Введите последовательность(для выхода введите '.' или 'буквенные символы'\n" << endl;
                    cout << "Информационные поля вершин дерева: " << endl;
                            while(cin>> el)
                                {
                                    add_bin_tree (el);
                                }
                break;
 
                case '2':
                    cout << "Если вы видите только надпись: 'Так выглядит дерево:', значит дерево пусто!\n" << endl;
                    cout << "Так выглядит дерево:\n" << endl;
                    
                        printtree (pHead, 0);
                break;
 
                case '3':
                    // вызов функции удаления
                break;
 
                case '4':
                    exit = true;
                break;
            
                default:
                    exit = true;
            }
    }
    fail.close();
    return 0;
}
//--------------------------------------------------------------------------------------------------------------------------
void addnode(bin_tree* tree, int value) // добавление конкретного узла(node - узел) дерева
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // если значение меньше, двигаемся по "левой ветке"
            addnode(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // иначе двигаемся по правой 
    { 
        if(tree->right != NULL)
            addnode(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " Эл-т уже присутствует в дереве"<< endl;
}
//------------------------------------------------------------------------------------------------------------------------- 
void add_bin_tree(int value)
{
    if(pHead == NULL) // если дерево пустое - создадим первый узел
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        addnode(pHead, value); // если в вершине уже что-то есть - добавляем слева или справа 
}
//------------------------------------------------------------------------------------------------------------------------- 
void obhod(bin_tree* tree, ofstream &fail)
{     
    if (tree != NULL)
    { 
        obhod(tree->left, fail);
        fail<< tree->value<< " ";
        obhod(tree->right, fail);
    }
}
//------------------------------------------------------------------------------------------------------------------------
// Выод дерева на экран
void printtree(bin_tree* tree, int Length)
{     
    if (tree != NULL)
    { 
        printtree(tree->left, Length + 1);     // вывод левого поддерева
        for(int i = 0; i < Length; i++) 
            {
                cout << "--";
            }
        cout << "Уровень: " << Length << "; Элемент = "; cout << tree->value << endl;
        //cout<< tree->value<< endl;       // вывод корня подерева
        printtree(tree->right, Length + 1);            // вывод левого поддерева
    }
}
//-------------------------------------------------------------------------------------------------------------------------
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2012, 12:08     Удаление вершины дерева поиска
Посмотрите здесь:

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

Выделение памяти для поддерева(вершины) бинарного дерева поиска - C++
как выделить память под вершину бинарного дерева? Почему у меня неверно выделяется память? class tree { public: tree(); ...

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

Некорректное удаление элемента бинарного дерева поиска - C++
Задача состоит в том, чтобы удалить максимальный в левом поддереве элемент и все его порожденные элементы. Я нахожу этот элемент и...

Вывести все вершины двоичного дерева - C++
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на экран? Набросайте, кому не трудно алгоритм) просто...

не листовые вершины бинарного дерева, где находятся? - C++
этими вершинами не являются ли сами листья дерева?

Объединение функций, которые выводят внешне вершины дерева - C++
Здравствуйте. Вот у меня есть 2 функции, которые выводит внешне вершины дерева, (одна правые, другая левые). void...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
30.06.2012, 12:28     Удаление вершины дерева поиска #2
Если брать удаление произвольного элемента, то задача решается в несколько этопов
1) Поиск элемента для удаления.
2) Для разного кол-ва детей надо выполнять разные действия.
а) Если у него нет детей, то надо просто освободить память и почистить указатель у родителя
б) Если есть только левый, то на место текущего ставится он.
в) Если есть только правый, то на место текущего ставится он.
г) Если есть левый и правый, то на роль новой вершины подойдет крайний левый у правого. Стоит не забыть, что у этого крайнего левого, может быть правый, который нужно будет поставить вместо перемещаемого.
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
30.06.2012, 12:32  [ТС]     Удаление вершины дерева поиска #3
Ну что-то подобное я написал, но оно не работает

uz - узел
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
void delElement(bin_tree *uz)
{
    bin_tree * temp;
    if( (uz->right != NULL || uz->left != NULL))
    {
        if(uz->left == NULL && uz->right == NULL && uz->parent == NULL)
         {
            if(uz==uz->parent->right)
               uz->parent->right = NULL;
            else
               uz->parent->left = NULL;
            delete uz;
         }
        else if(uz->left == NULL && uz->right != NULL)
         {
            uz->right->parent = uz->parent;
            uz->parent = uz->right;
            delete uz;            
         }
         else if(uz->left != NULL && uz->right == NULL)
         {
            uz->left->parent=uz->parent;
            uz->parent=uz->left;
            delete uz;            
         }
         else if(uz->left != NULL && uz->right != NULL)
         {
            uz->right->parent=uz->parent;
            temp=uz->right;
            while(temp->left != NULL)
                  temp = temp->left;
            temp->left = uz->left;
            uz->left->parent = temp;
            delete uz;            
         }
    }
    else
    {
        if(uz->left == NULL && uz->right == NULL && uz->parent == NULL)
        {
     delete uz;                      
        }
        else if(uz->left==NULL && uz->left == NULL && uz->parent != NULL) 
        {
     if(uz->parent->left == uz)
        uz->parent->left = NULL;
     else
     uz->parent->right = NULL;  
     delete uz;                      
        }  
        else if(uz->left != NULL && uz->right == NULL)
        {
           uz->left->parent = NULL;
           pHead = uz->left;
           delete uz;           
        }
        else if(uz->left == NULL && uz->right != NULL)
        {
           uz->right->parent = NULL;
           pHead = uz->right;
           delete uz;           
        }
        else if(uz->left != NULL && uz->right != NULL)
        {
           uz->right->parent = NULL;
           pHead = uz->right;
           temp = uz->right;
           while(temp->left != NULL)
                 temp = temp->left;
           temp->left = uz->left;
           uz->left->parent=temp;
           delete uz;           
        }
    }
    
    printf("Удаленный:  эл-т = %d;\n", uz);
}
neske
1479 / 846 / 75
Регистрация: 26.03.2010
Сообщений: 2,902
30.06.2012, 12:35     Удаление вершины дерева поиска #4
рекурсивная функция
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void del(node *&cur) { 
    if (cur->left == NULL || cur->right == NULL) { // если есть один потомок, или их вообще нет
        node* sav = cur;
        if (cur->left != NULL) // перетаскиваем потомка на место вершины, а саму вершину удаляем
            cur = cur->left;
        else
            cur = cur->right;
        delete sav;
    } else { // дальше идет процедура удаления, если у вершины есть оба потомка
        node** p2 = &cur->right;
        while ((*p2)->left) p2 = &((*p2)->left);
        cur->key = (*p2)->key;
        del(*p2);
    }
}
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
30.06.2012, 12:36     Удаление вершины дерева поиска #5
C++
1
2
3
if(uz->left == NULL && uz->right == NULL && uz->parent == NULL)
{
   if(uz==uz->parent->right)
Уже странно, если у него нет родителя, то как у его родителя может быть правый?

У меня есть пример реализации на основе двойных указателей. Но основная проблема в том, что он сделан для дерева, в узле которого нет указателя на родителя. Но не думаю, что он тебе будет понятен((
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
30.06.2012, 12:36  [ТС]     Удаление вершины дерева поиска #6
Вот, поиск. (стоит до main)

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
// Поиск
bin_tree *Search( bin_tree *koren, int element )/* рекурсивная функция поиска узла по значению*/
{
   if (koren == NULL)
       {
           return NULL;
    }
   else
       {
           if (koren->izyatiya==element)
           { 
               printf("Search adr =%d\n;",koren); return koren;
           }
    else
        {
            if (element < koren->izyatiya) 
                {
                    return Search(koren->left, element);
                }
    else
        {
            return Search(koren->right, element);
        }
        } 
        }
}
Но когда вызываю

C++
1
2
3
4
5
6
7
case '4':
                    printf( "Введи указатель\n" );
                    scanf( "%d", &item );
                    
                    delElement(Search(pHead, item));
                    // вызов функции удаления
                break;
Вылезает ошибка прав доступа. (скорее всего из-за памяти, но не пойму где)
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
30.06.2012, 12:38     Удаление вершины дерева поиска #7
Да и почти везде ты забываешь про указатели. Ты вроде нигде не перебрасываешь указатели с удаляемого элемента на новый. Не сделано то, что я упомянул в 2 г.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2012, 12:39     Удаление вершины дерева поиска
Еще ссылки по теме:

Пронумеровать вершины бинарного дерева в соответствии с порядком концевого обхода - C++
Здравствуйте!!!! Помогите пожалуйста решить задачу. Построить бинарное дерево поиска для заданного множества целых чисел и занумеровать...

Определение глубины (числа ветвей) непустого дерева от вершины до заданного узла - C++
Подскажите пожалуйста. Никак не могу найти код нахождения глубины бинарного дерева от вершины до заданного узла. тут весь форум перерыл...

Для каждой вершины бинарного дерева, поменять местами дочерние элементы - C++
Дано бинарное дерево.(заполняется с клавиатуры). Для каждой вершины, имеющей дочернюю, поменять местами дочерние. Меняем только значения. ...

Вершины дерева вещественные числа. Описать процедуру, которая вычисляет среднее арифметическое всех вершин - C++
Вершины дерева вещественные числа. Описать процедуру, которая вычисляет среднее арифметическое всех вершин дерева и добавляет в дерево...

Записи вершин дерева - вещественные числа. Описать процедуру, которая выбирает все вершины с отрицательными за - C++
Записи вершин дерева - вещественные числа. Описать процедуру, которая выбирает все вершины с отрицательными записями и строит из них новое...


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

Или воспользуйтесь поиском по форуму:
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
30.06.2012, 12:39  [ТС]     Удаление вершины дерева поиска #8
darkknight2008, Спасибо, попробую исправить сейчас
Yandex
Объявления
30.06.2012, 12:39     Удаление вершины дерева поиска
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru