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

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

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

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

30.06.2012, 12:08. Просмотров 1224. Ответов 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);            // вывод левого поддерева
    }
}
//-------------------------------------------------------------------------------------------------------------------------
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2012, 12:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление вершины дерева поиска (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
30.06.2012, 12:28 #2
Если брать удаление произвольного элемента, то задача решается в несколько этопов
1) Поиск элемента для удаления.
2) Для разного кол-ва детей надо выполнять разные действия.
а) Если у него нет детей, то надо просто освободить память и почистить указатель у родителя
б) Если есть только левый, то на место текущего ставится он.
в) Если есть только правый, то на место текущего ставится он.
г) Если есть левый и правый, то на роль новой вершины подойдет крайний левый у правого. Стоит не забыть, что у этого крайнего левого, может быть правый, который нужно будет поставить вместо перемещаемого.
0
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);
}
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
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);
    }
}
0
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)
Уже странно, если у него нет родителя, то как у его родителя может быть правый?

У меня есть пример реализации на основе двойных указателей. Но основная проблема в том, что он сделан для дерева, в узле которого нет указателя на родителя. Но не думаю, что он тебе будет понятен((
0
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;
Вылезает ошибка прав доступа. (скорее всего из-за памяти, но не пойму где)
0
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
30.06.2012, 12:38 #7
Да и почти везде ты забываешь про указатели. Ты вроде нигде не перебрасываешь указатели с удаляемого элемента на новый. Не сделано то, что я упомянул в 2 г.
0
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
30.06.2012, 12:39  [ТС] #8
darkknight2008, Спасибо, попробую исправить сейчас
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2012, 12:39
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.06.2012, 12:39
Ответ Создать тему
Опции темы

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