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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
nxexox
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 48
#1

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

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

Здравствуйте программисты! Учусь на первом курсе. Возникли проблемы с разработкой функции удаления ветки листа или корня из дерева. Т.е. удаление из дерева по ключу любого элемента. код не работает. три дня сижу запарился с ней. Помогите пожалуйста
вот код:
Кликните здесь для просмотра всего текста
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;
 
        }
    }*/
 
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2014, 16:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция удаления листа (или ветки) бинарного дерева (C++):

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

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

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

Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) - C++
Здравствуйте! Помогите, пожалуйста, в написании функции ,которая получает указатель на корень дерева и возвращает длинну самой длинной...

Функция вывода листьев бинарного дерева - C++
Написал функцию вывода всего что есть в дереве. помогите переделать ее так чтобы она выводила только листья(без детей которые) void...

Функция подсчета четных элементов бинарного дерева - C++
Требуется написать функцию подсчета количества четных узлов бинарного дерева

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
Ушёл с форума.
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
Ушёл с форума.
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
Ушёл с форума.
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
Ушёл с форума.
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
Ушёл с форума.
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, 18:33
Привет! Вот еще темы с ответами:

Функция удаления элемента из дерева - C++
В данной программе реализовано почти все,кроме фунции удаления,которую я так и не смог реализовать. Руководствуюсь методами: -если это...

Функция удаления элемента из дерева, ошибка в коде - C++
Добрый вечер, уважаемые программисты! :) Помогите, пожалуйста, понять где здесь ошибка. static bool h = false; // узел...

Функция удаления всех четных элементов AVL-дерева - C++
Помогите допилить функцию удаления всех парных элементов АВЛ дерева. Она сейчас удаляет только элементы, которые находятся в правой...

Определить длину бинарного (или произвольного) дерева - C++
Определите длину бинарного(или произвольного) дерева (т.е. длину максимальной ветви) Visual studio c++, консольный режим. Можно пожаласт...


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

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

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