0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
1

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

18.05.2014, 16:32. Показов 11552. Ответов 15
Метки нет (Все метки)

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
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;
 
        }
    }*/
 
 
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.05.2014, 16:32
Ответы с готовыми решениями:

Вывод левой ветки бинарного дерева
Здравствуйте, уважаемые форумчане! Вывел левую ветку бинарного дерева на экран, но хотел...

Нужно вывести на экран содержимое самой длинной ветки бинарного дерева
Нужно вывести на экран содержимое самой длинной ветки бинарного дерева на c++

Как сравнить между собой ветки бинарного дерева?
Ребят, как сравнить между собой ветки бинарного дерева, точнее сравнить правую ветку с левой и так...

Удаление листа бинарного дерева
Есть бинарное дерево, в нем нужно удалить все элементы с заданым значением. В каждом узле ссылка...

15
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 16:34 2
Что за загадочная ветка листа? Не изобретай прорывов в биологии.
0
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:36  [ТС] 3
Ветка это лист с детьми. нам так преподаватель объяснял. у листа нет потомков, у ветки есть 1 или два потомка, а корень это начало дерева
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 16:46 4
Я знаю, что такое ветвь дерева и лист. Мне не понятно, что такое ветка листа.

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

Добавлено через 2 минуты
Цитата Сообщение от nxexox Посмотреть сообщение
Возникли проблемы с разработкой функции удаления ветки , листа или корня из дерева.
Исправил опечатку
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 16:52 6
Ветвь - это часть дерева, содержащая несколько узлов дерева, причём, каждый узел ветви кроме одного является непосредственным потомком (ребёнком) другого узла той же ветви и каждый узел ветви кроме одного является непосредственным предком (родителем) ровно одного другого узла той же ветви. То есть ветвь есть поддерево, вырожденное в линейный список.
0
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:52  [ТС] 7
Цитата Сообщение от taras atavin Посмотреть сообщение
Ветвь - это часть дерева, содержащая несколько узлов дерева, причём, каждый узел ветви кроме одного является непосредственным потомком (ребёнком) другого узла той же ветви и каждый узел ветви кроме одного является непосредственным предком (родителем) ровно одного другого узла той же ветви. То есть ветвь есть поддерево, вырожденное в линейный список.
Это я понимаю.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 16:56 8
Тогда должен понимать, что потомков она не имеет, так как она - не отдельный узел, а совокупность узлов.
0
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 16:57  [ТС] 9
Ты сможешь мне помочь?
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 16:57 10
У мера могут быть дети, у города нет. Дети могут быть жителями города, но это дети других людей, ни как не города.
0
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 17:17  [ТС] 11
Люди, помогите пожалуйста
0
71 / 45 / 24
Регистрация: 11.05.2014
Сообщений: 179
18.05.2014, 17:37 12
Люди-то помогут, да вот алгоритм у Вас кривой изначально.

1. При удалении не учитывается, что удаляемых элементов с одинаковым ключом может быть
несколько.
2. После удаления должна производиться балансировка дерева, а у Вас же ТОЛЬКО удаляется лист дерева, а если попали не на лист, тогда что??
3. Кто же рекурсию использует при работе с большими деревьями?? А если стэк переполнится??
0
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
18.05.2014, 17:42  [ТС] 13
Дак вот в этом то и проблема, я 5 раз с нуля пробовал переписывать функцию, на пятый психанул и пошел сюда с незаконченной функцией. я как думаю. для начала нужно сделать функцию удаления общую, потом ее улучшать и модернизировать. т.е. сначала сделать что б удаляла хоть правильно а потом уже предусматривать всякие случаи.
а проблема в том то и есть что не удаляет правильно, эта незаконченная вообще не удаляет
0
71 / 45 / 24
Регистрация: 11.05.2014
Сообщений: 179
18.05.2014, 17:45 14
http://ru.wikipedia.org/wiki/%... 8REMOVE.29
тут все разжевано
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
18.05.2014, 18:33 15
Цитата Сообщение от helper Посмотреть сообщение
2. После удаления должна производиться балансировка дерева,
Кто сказал? Мало ли для каких целей у него дерево? Может ключ непосредственно отражает положение в дереве?

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

Добавлено через 2 минуты
Цитата Сообщение от helper Посмотреть сообщение
А если стэк переполнится??
Даже если дерево и может иметь тысячи уровней, то при гигантской памяти. В ней проблема раздуть стек до пары гуглов зеттабайт? Не верю.
0
97 / 71 / 12
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 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. Лучшее объяснение двоичных деревьев находил в Кормене когда-то давно.
0
18.05.2014, 19:24
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.05.2014, 19:24
Помогаю со студенческими работами здесь

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

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

Итерационный метод удаления бинарного дерева
Есть бинарное дерево поиска нужно создать итерационный метод удаления дерева. Вот есть функция...

Написать подпрограмму удаления элемента из бинарного дерева
...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru