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

Функция удаления листа (или ветки) бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:32     Функция удаления листа (или ветки) бинарного дерева #1
Здравствуйте программисты! Учусь на первом курсе. Возникли проблемы с разработкой функции удаления ветки листа или корня из дерева. Т.е. удаление из дерева по ключу любого элемента. код не работает. три дня сижу запарился с ней. Помогите пожалуйста
вот код:
Кликните здесь для просмотра всего текста
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
#include <iostream>
using namespace std;
 
 
struct Node   
 { int d;
   Node *l; 
   Node *r; 
 };
void add(Node*& p, int d);
void print( Node* p, int level=1 );
void del(Node* p,int key);
Node* firstpr(Node* p,int key);
Node* first(Node* p,int key);
 
void main()
{ Node* p, pv;
  int b[] = {10, 25, 20, 6, 21, 8, 1, 30};
  p = NULL;
  //cout <<"vvedite 4isla ";
  for(int i=0;i<8;i++) add(p,b[i]);
  cout<<endl;
   print( p );
   cout <<"\n\n"; 
  del(p,1);
  print(p);
  system("pause");
}
 
void add(Node*& p, int d) 
 
{ if (p == NULL)  
   { p = new Node; p->l = NULL; p->r = NULL; p->d = d; }
   else             
    { if (d >= p->d) add(p->r, d);  
      if (d <  p->d) add(p->l, d);   
    }
}
 
void print( Node* p, int level ) 
{ int tab = 5; 
 
  if (p == NULL) cout <<"Derevo pusto \n";
   else
    { if (p->r != NULL) print(p->r, level+1);
                
      cout.width(tab*level);
      cout<<p->d <<endl;
      if (p->l != NULL) print(p->l, level+1);
    }
}
 
Node* firstpr(Node* p,int key)
{
    if(p->l->d==key) return p;
    if(p->r->d==key) return p;
    if(key<p->d) firstpr(p->l,key);
    if(key>p->d) firstpr(p->r,key);
}
Node* first(Node* p,int key)
{
    Node* pv=firstpr(p,key);
    if(pv->l->d==key) return pv->l;
    if(pv->r->d==key) return pv->r;
}
 
void del(Node* p,int key)
{
    Node* pd1;
    Node* pr=firstpr(p,key);
    Node* pd=first(p,key);
    if((pd->r==NULL)&&(pd->l==NULL))
    {
        if(pr->r==pd) pr->r=NULL;
        else if(pr->l==pd) pr->l=NULL;
        delete pd;
    }
    /*else if(pd->l==NULL)
    {
        
        if(pr->r==pd)pr->r=pd->r;
        if(pr->l==pd)pr->l=pd->r;
        pd->r=NULL;
        delete pd;
    }
    else if(pd->r==NULL)
    {
        
        if(pr->r==pd)pr->r=pd->l;
        if(pr->l==pd)pr->l=pd->l;
        pd->l=NULL;
        delete pd;
    }*/
    /*else
    {
        if(pd->r->l==NULL)
        {
            if(pr->r=pd)pr->r=pd->r;
            if(pr->l=pd)pr->l=pd->r;
            pd->r=NULL;
            delete pd;
        }
        else
        {
            pd1=pd;
            pd1=pd1->r;
            while(pd1->l->l=NULL) pd1=pd1->l;
            pd1->l->l=pd->l;
 
        }
    }*/
 
 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 16:34     Функция удаления листа (или ветки) бинарного дерева #2
Что за загадочная ветка листа? Не изобретай прорывов в биологии.
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:36  [ТС]     Функция удаления листа (или ветки) бинарного дерева #3
Ветка это лист с детьми. нам так преподаватель объяснял. у листа нет потомков, у ветки есть 1 или два потомка, а корень это начало дерева
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 16:46     Функция удаления листа (или ветки) бинарного дерева #4
Я знаю, что такое ветвь дерева и лист. Мне не понятно, что такое ветка листа.

Добавлено через 2 минуты
Кстати, потомки бывают у узлов, а не ветвей.
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:51  [ТС]     Функция удаления листа (или ветки) бинарного дерева #5
Я опечатался. Прошу прощения. Переформулирую то что написал в самом начале. У меня не получается написать функцию удаления, которая будет удалять как лист так и ветку. т.е. элемент с потомками и без потомков. Причем удаление с потомками происходит по след алгоритму: от удаляемого элемента спускаемся вправо 1 раз, и потом влево до того момента пока влево не кончатся связи. и этот элемент ставим на место удаляемого

Добавлено через 2 минуты
Цитата Сообщение от nxexox Посмотреть сообщение
Возникли проблемы с разработкой функции удаления ветки , листа или корня из дерева.
Исправил опечатку
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 16:52     Функция удаления листа (или ветки) бинарного дерева #6
Ветвь - это часть дерева, содержащая несколько узлов дерева, причём, каждый узел ветви кроме одного является непосредственным потомком (ребёнком) другого узла той же ветви и каждый узел ветви кроме одного является непосредственным предком (родителем) ровно одного другого узла той же ветви. То есть ветвь есть поддерево, вырожденное в линейный список.
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:52  [ТС]     Функция удаления листа (или ветки) бинарного дерева #7
Цитата Сообщение от taras atavin Посмотреть сообщение
Ветвь - это часть дерева, содержащая несколько узлов дерева, причём, каждый узел ветви кроме одного является непосредственным потомком (ребёнком) другого узла той же ветви и каждый узел ветви кроме одного является непосредственным предком (родителем) ровно одного другого узла той же ветви. То есть ветвь есть поддерево, вырожденное в линейный список.
Это я понимаю.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 16:56     Функция удаления листа (или ветки) бинарного дерева #8
Тогда должен понимать, что потомков она не имеет, так как она - не отдельный узел, а совокупность узлов.
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:57  [ТС]     Функция удаления листа (или ветки) бинарного дерева #9
Ты сможешь мне помочь?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 16:57     Функция удаления листа (или ветки) бинарного дерева #10
У мера могут быть дети, у города нет. Дети могут быть жителями города, но это дети других людей, ни как не города.
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 17:17  [ТС]     Функция удаления листа (или ветки) бинарного дерева #11
Люди, помогите пожалуйста
helper
70 / 44 / 18
Регистрация: 11.05.2014
Сообщений: 176
18.05.2014, 17:37     Функция удаления листа (или ветки) бинарного дерева #12
Люди-то помогут, да вот алгоритм у Вас кривой изначально.

1. При удалении не учитывается, что удаляемых элементов с одинаковым ключом может быть
несколько.
2. После удаления должна производиться балансировка дерева, а у Вас же ТОЛЬКО удаляется лист дерева, а если попали не на лист, тогда что??
3. Кто же рекурсию использует при работе с большими деревьями?? А если стэк переполнится??
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 17:42  [ТС]     Функция удаления листа (или ветки) бинарного дерева #13
Дак вот в этом то и проблема, я 5 раз с нуля пробовал переписывать функцию, на пятый психанул и пошел сюда с незаконченной функцией. я как думаю. для начала нужно сделать функцию удаления общую, потом ее улучшать и модернизировать. т.е. сначала сделать что б удаляла хоть правильно а потом уже предусматривать всякие случаи.
а проблема в том то и есть что не удаляет правильно, эта незаконченная вообще не удаляет
helper
70 / 44 / 18
Регистрация: 11.05.2014
Сообщений: 176
18.05.2014, 17:45     Функция удаления листа (или ветки) бинарного дерева #14
http://ru.wikipedia.org/wiki/%C4%E2%...0_.28REMOVE.29
тут все разжевано
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.05.2014, 18:33     Функция удаления листа (или ветки) бинарного дерева #15
Цитата Сообщение от helper Посмотреть сообщение
2. После удаления должна производиться балансировка дерева,
Кто сказал? Мало ли для каких целей у него дерево? Может ключ непосредственно отражает положение в дереве?

Добавлено через 1 минуту
Цитата Сообщение от helper Посмотреть сообщение
3. Кто же рекурсию использует при работе с большими деревьями?? А если стэк переполнится??
А как же без рекурсии работать с деревом? Оно само рекурсивно:
Поддерево есть часть дерева, сама являющаяся деревом.
.

Добавлено через 2 минуты
Цитата Сообщение от helper Посмотреть сообщение
А если стэк переполнится??
Даже если дерево и может иметь тысячи уровней, то при гигантской памяти. В ней проблема раздуть стек до пары гуглов зеттабайт? Не верю.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.05.2014, 19:24     Функция удаления листа (или ветки) бинарного дерева
Еще ссылки по теме:

C++ Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве)
C++ Удаления узла из бинарного дерева поиска
Функция подсчета четных элементов бинарного дерева C++

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

Или воспользуйтесь поиском по форуму:
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
18.05.2014, 19:24     Функция удаления листа (или ветки) бинарного дерева #16
Ваш код, подредактированный и работающий - всё узлы дерева последовательно удаляются, начиная с любого.

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
#include <iostream>
using namespace std;
 
 
struct Node { 
    int value;
    Node *left; 
    Node *right; 
};
 
void add(Node*& p, int value);
void print( Node* p, int level=1 );
Node *del(Node* p,int key);
 
void main() { 
    Node *root = NULL;
    int b[] = {10, 25, 20, 6, 21, 8, 1, 30};
    //cout <<"vvedite 4isla ";
    for( int i = 0; i < 8; i++ ) {
        add(root, b[i]);
    }
 
    for( int i = 0; i < 8; i++ ) {
        cout <<"\n\n"; 
        root = del(root, b[i]);
        print(root);
    }
       
    system("pause");
}
 
void add(Node*& p, int value) { 
    if (p == NULL) {
        p = new Node; 
        p->left = NULL; 
        p->right = NULL; 
        p->value = value; 
    } else { 
        if( value < p->value ) {
            add(p->left, value);  
        } else if( value > p->value ) {
            add(p->right, value);  
        }
    }
}
 
void print( Node* p, int level ) { 
    if( p != NULL ) {
        cout << "Level " << level << ", Value: " << p->value << endl;
    } else if( level == 1 ){
        cout << "Empty tree!" << endl;
        return;
    }
    if( p->left != NULL ) {
        print(p->left, level + 1);
    }
    if( p->right != NULL ) {
        print(p->right, level + 1);
    }
}
 
Node* search(Node* p, int key) {
    if( p == NULL ) { 
        return NULL;
    }
 
    if( key == p->value ) {
        return p;
    } else if( key < p->value ) {
        return search(p->left, key);
    } else {
        return search(p->right, key);
    }
}
 
Node *parent(Node *p, Node *del_p, int key) {
    if( p == NULL ) {
        return NULL;
    }
    if( p->left == del_p || p->right == del_p || p == del_p ) {
        return p;
    }
 
    if( key < p->value ) {
        return parent(p->left, del_p, key);
    } else {
        return parent(p->right, del_p, key);
    }
}
 
Node* find_ld(Node *p) {
    if( p == NULL ) {
        return NULL;
    }
    if( p->left != NULL ) {
        return find_ld(p->left);
    }
    return p;
}
 
Node *del(Node* p, int key) {
    if( p->left == NULL && p->right == NULL ) {
        delete p;
        return NULL;
    }
 
    Node *root = p;
 
    Node* del_p = search(p, key);
    Node* pd = parent(p, del_p, key);
 
    Node* ld = find_ld(del_p->right);
    
    if( ld == NULL ) {
        if( pd->left == del_p ) {
            pd->left = del_p->left;
        } else {
            pd->right = del_p->right;
        }
 
        delete del_p;
        return p;
    }
    Node* pld = parent(p, ld, ld->value);
    
    if( pd == del_p ) {
        pd = ld;
        root = NULL;
    } else if( pd->left == del_p ) {
        pd->left = ld;
    } else {
        pd->right = ld;
    }
 
    if( pld->left == ld ) {
        pld->left = ld->right;
        ld->left = del_p->left;
        ld->right = del_p->right;
    } else {
        pld->right = ld->right;
        ld->left = del_p->left;
    }
 
    delete del_p;
    return (root == NULL)? pd: root;
}
P.S. Для удаления узла, если прямой ссылки на родителя нет (как в данном случае), необходимо знать следующие узлы:
1) Узел, который удаляем
2) Родительский узел узла 1
3) Самый левый лист в правой поддереве узла 1
4) Родительский узел узла 3

P.P.S. Лучшее объяснение двоичных деревьев находил в Кормене когда-то давно.
Yandex
Объявления
18.05.2014, 19:24     Функция удаления листа (или ветки) бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 15:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru