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

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

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

Деревья - C++

22.07.2012, 02:13. Просмотров 969. Ответов 14
Метки нет (Все метки)

Я не особо разбираюсь в программировании (т.к это не связано с моей будущей специальностью,но те кто составлял учебный курс так не считают )поэтому не бросайтесь камнями.
Суть задания:
"Информационное поле двоичного упорядоченного дерева содержит целое число.Удалить из дерева все узлы,информационное поле которых превышает некоторое вводимое пользователем число."
У меня возникли некоторые сложности:
1.Не представляю как должна работать функция для удаления.
2.Компилятор выдаёт не понятные для меня ошибки.
Вот,что я смог осилить,заранее спасибо:
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
#include <iostream.h>
#include <stdio.h>
#include <windows.h>
 
struct Node {
  int  data;          
  Node *left, *right; 
  };
typedef Node *PNode;
 
void AddToTree (PNode &Tree, int x) // построение дерева
{
if ( ! Tree ) {
   Tree = new Node;
   Tree->data = x;
   Tree->left = NULL;
   Tree->right = NULL;
   return;
   }
if ( x < Tree->data )
     AddToTree ( Tree->left, x );
else AddToTree ( Tree->right, x );
}
 
 
PNode Search (PNode Tree, int x) // поиск ключа
{
if ( ! Tree ) return NULL;
if ( x == Tree->data ) 
     return Tree;
if ( x < Tree->data )
  return Search(Tree->left, x);
else 
  return Search(Tree->right, x);
}
 
int main ()
{SetConsoleOutputCP(1251);
int x,n,i;
Node *root=NULL;
printf("Введите количество узлов дереве: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{cin>>x;
root=AddToTree(root,x);}
Search(root,x);
return 0;}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2012, 02:13     Деревья
Посмотрите здесь:

Деревья - C++
Написать программу, которая вводит с клавиатуры сбалансированное дерево и считает сумму элементов дерева.

деревья на С++ - C++
эта задачка на деревья.помогите пожалуйста...от этого зависит мой экзамен... В школе продолжительность каждого урока 45 минут, а перемены...

деревья - C++
Доброго дня всем. Подскажите плиз что не правильно, пытаюсь разобраться в деревьях и шаблонах. Есть 2 класса лист и дерево, по...

Деревья на с++ - C++
Задание: Напишите программу, содержащую процедуру или функцию, которая подсчитывает число вершин на каждом уровне непустого дерева...

Деревья - C++
Создать процедуру построения бинарного дерева на основе не бинарного. Заранее спасибо.

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

Деревья - C++
Здравствуйте. Помогите разобраться с деревьями. Можно бинарное, можно не бинарное.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rudeeeboy
14 / 14 / 1
Регистрация: 08.11.2010
Сообщений: 172
22.07.2012, 02:19     Деревья #2
1.Не представляю как должна работать функция для удаления.
дерево обнули
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
22.07.2012, 02:29  [ТС]     Деревья #3
Цитата Сообщение от rudeeeboy Посмотреть сообщение
1.Не представляю как должна работать функция для удаления.
дерево обнули
можно подробнее,пожалуйста?
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
22.07.2012, 06:11     Деревья #4
Ошибки, которые на виду.
Цитата Сообщение от reznov Посмотреть сообщение
root=AddToTree(root,x);}
Функция у вас определена, как невозвращающая значение (void), хотя в ней (строка 18) присутствует некий return. Если присваиваете возвращаемое значение root, то функция должна возвращать значение типа *PNode.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 06:52     Деревья #5
Цитата Сообщение от reznov Посмотреть сообщение
можно подробнее,пожалуйста?
Функция удаления узла имеешь ввиду? Она неоднозначна. У меня была такая задача в лабе по проге. Прикрепил её к сообщению. Собственно, DeleteNode - то, что тебе нужно почитать
upd. Файл не прикрепился, поэтому кодом :
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
/*
9 - Двоичные деревья
22*. Из входной последовательности чисел построить двоичное дерево и удалить узел, содержащий значение х (х вводится с клавиатуры).
*/
#include <conio.h>
#include <iostream>
#include <fstream>
#include <locale.h>
int flag = 0;
struct TREE
{
    int number, amount;
    TREE *leftLink, *rightLink;
};
 
TREE *CreateTree (TREE *currentNode, int enteredNumber)
{
    if (currentNode==NULL)
    {
        currentNode=new TREE;
        currentNode->rightLink=currentNode->leftLink=NULL;
        currentNode->amount=1;
        currentNode->number=enteredNumber;
    }
    else
        if (enteredNumber<currentNode->number)
        {
            currentNode->leftLink=CreateTree(currentNode->leftLink,enteredNumber);
        }
        else
            if (enteredNumber>currentNode->number)
            {
                currentNode->rightLink=CreateTree(currentNode->rightLink,enteredNumber);
            }   
            else
                if (enteredNumber==currentNode->number)
                {
                    currentNode->amount++;
                }
    return currentNode;
}
int child (TREE* node)
{
    int children = 0;
    if (node->leftLink) children--;
    if (node->rightLink) children+=2;
    return children;
}   
void DeleteNode (TREE* foundedNode, TREE* parentNode)
{
    TREE* currentNode;
    if (child(foundedNode) == 1)
    {
        currentNode = foundedNode->rightLink;
        while (currentNode->leftLink)
            currentNode = currentNode->leftLink;
        currentNode->leftLink = foundedNode->leftLink;
        if (parentNode->leftLink == foundedNode)
            parentNode->leftLink = foundedNode->rightLink;
        else
            parentNode->rightLink = foundedNode->rightLink;
        delete foundedNode;
    }
    else
        if (child(foundedNode) == -1)
        {
            if (parentNode->leftLink == foundedNode)
                parentNode->leftLink = foundedNode->leftLink;
            else
                parentNode->rightLink = foundedNode->leftLink;
            delete foundedNode;
        }
        else
        {
            if (parentNode->leftLink == foundedNode)
                parentNode->leftLink = foundedNode->rightLink;
            else
                parentNode->rightLink = foundedNode->rightLink;
            delete foundedNode;
        }
}
void FindNode (int number, TREE* currentNode, TREE* lastNode)
{
    if (flag) 
        return;
    else
        if (currentNode)
        {
            if (currentNode->number == number)
            {
                flag = 1;
                DeleteNode (currentNode, lastNode);
                return;
            }
            else
            {
                FindNode(number, currentNode->leftLink, currentNode);
                FindNode(number, currentNode->rightLink, currentNode);
                return;
            }
        }
}
void main()
{
    setlocale(0,"");
    std::ifstream in("input.txt");
 
    int enteredNumber;
    in >> enteredNumber;
    TREE *top=new TREE;
    top->number=enteredNumber;
    top->leftLink=top->rightLink=NULL;
    top->amount=1;
 
    while (!in.eof())
    {
        in >> enteredNumber;
        CreateTree(top,enteredNumber);
    }
 
    std::cout << "Введите искомое число : " << std::endl;
    int nodeNumber;
    std::cin >> nodeNumber;
 
    FindNode(nodeNumber, top, NULL); 
 
    if (flag == 0) 
    {
        std::cout << "Узел не найден!" << std::endl;
        _getch();
        return;
    }
 
    std::cout << "Дерево было перестроено!" << std::endl;
 
    _getch();
}
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
22.07.2012, 07:45     Деревья #6
Код
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
#include <iostream>
#include <windows.h>
using namespace std; 
 
struct Tree 
 {
  int data;
  struct Tree *left;
  struct Tree *right;
};
 
// создает упорядоченное двоичное дерево.
Tree *AddToTree(Tree *root, Tree *r, int x)
{
  if(!r) 
  {
    r = new Tree;
    if(!r) 
    {
      printf("Не хватает памяти\n");
      exit(0);
    }
    r -> left = NULL;
    r -> right = NULL;
    r -> data = x;
    if (!root) return r; // первый вход.
    if (x < root -> data) root -> left = r;
    else root -> right = r;
    return r;
  }
  if (x < r -> data)
     AddToTree(r, r -> left, x);
  else
     AddToTree(r, r -> right, x);
 
  return root; 
}
 
// обход дерева в симметричном порядке и вывод поля data.
void inorder(Tree *root)
{
  if(!root) return;
 
  inorder(root -> left);
  if (root -> data) cout << root -> data << endl;
  inorder(root -> right);
}
 
int main ()
{
 
SetConsoleOutputCP(1251);
 
Tree *root = NULL;
 
cout << "Введите количество узлов деревa: ";
 
int n;
cin >> n;
 
int x = 0;
for(int i = 0; i < n; i++)
{
    cout << "Введите значение узла: ";
    cin >> x;
    root = AddToTree(root, root, x);
}
 
inorder(root);
 
system("pause");
return 0;
}
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 07:26  [ТС]     Деревья #7
Ребят,спасибо вам огромное!
Кто подскажет мне,что такое информационное поле дерева?
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
24.07.2012, 07:39     Деревья #8
Цитата Сообщение от reznov Посмотреть сообщение
что такое информационное поле дерева?
В вашем коде это - int data;
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 17:39  [ТС]     Деревья #9
Цитата Сообщение от nexen Посмотреть сообщение
Функция удаления узла имеешь ввиду? Она неоднозначна. У меня была такая задача в лабе по проге. Прикрепил её к сообщению. Собственно, DeleteNode - то, что тебе нужно
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
24.07.2012, 18:25     Деревья #10
Цитата Сообщение от reznov Посмотреть сообщение
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
Почему же, можно, просто тогда я об этом не подумал, видимо. Или подумал, но не стал делать, так как из-за этого пришлось бы так же переписывать указатель на корень дерева.
Ошибка происходит из-за того, что я обращаются в потомкам parent-узла, коего корень не имеет, а посему parent == NULL.
neske
1474 / 841 / 74
Регистрация: 26.03.2010
Сообщений: 2,889
24.07.2012, 18:59     Деревья #11
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void del(node *&cur) { // удаление вершины из дерева.
    if (cur == NULL)
        return;
    if (cur->left == NULL || cur->right == NULL) {
        node *sav = cur;
        cur = (cur->left) ? cur->left : cur->right;
        delete sav;
        sav = NULL;
    } else {
        node** p = &cur->right;
        while ((*p)->left) p = &((*p)->left);
        cur->data = (*p)->data;
        del(*p);
    }
}
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
25.07.2012, 05:49  [ТС]     Деревья #12
Теперь появилась ещё одна проблема,если вводимый элемент меньше корня,то удаляется всё нормально,если больше то удаляются узлы с меньшим значением (должно быть наоборот).
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
#include <iostream>
#include <windows.h>
using namespace std; 
 
struct Tree 
 {
  int data;
  struct Tree *left;
  struct Tree *right;
};
 
Tree *AddToTree(Tree *root, Tree *r, int x)
{
 if(!r) 
  {
    r = new Tree;
    r -> left = NULL;
    r -> right = NULL;
    r -> data = x;
    if (!root) return r; 
    if (x < root -> data) root -> left = r;
    else root -> right = r;
    return r;
  }
  if (x < r -> data)
     AddToTree(r, r -> left, x);
  else
     AddToTree(r, r -> right, x);
 
  return root; 
}
 
 
 
void inorder(Tree *root,int l)
{
  if(!root) return;
 
  inorder(root -> left,l+5);
  if (root -> data) {for(int i=0;i<l;i++) cout<<" "; cout << root -> data << endl;}
  inorder(root -> right,l+5);
}
 void del(int data,Tree *&root) { 
    if (root == NULL)
        return;
    
if(root->data >= data)
    while (root->data >= data)
    {
    Tree *sav = root;
    
        root = (root->left);
delete sav;
        sav = root;
    }
 
    
    else 
    while (root->data < data)
    {
    Tree *sav = root;
    
            root = (root->right);
        delete sav;
        sav = root;
}
     
}
 
int main ()
{
 SetConsoleOutputCP(1251);
 Tree *root = NULL;
 cout << "Введите количество узлов деревa: ";
 int n,y,x[6];
cin >> n;
 for(int i = 0; i < n; i++)
{
    cout << "Введите значение узла: ";
    cin >> x[i];
    root = AddToTree(root, root, x[i]);
}
 inorder(root,0);
cout<<"\nВведите искомое число\n"<<endl;
cin>>y;
cout<<endl;
del(y,root);
inorder(root,0);
system("pause");
return 0;
}
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
25.07.2012, 07:57     Деревья #13
Несколько не понял, что удаляется? (Нет возможности запустить сейчас и проверить)
Насколько я помню, в моей программе удаляться должно все корректно, если узел не корень, и удаление происходит только одного узла, а не поддерева, просто происходит перестройка дереве
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
25.07.2012, 23:25  [ТС]     Деревья #14
Необходимо удалить из дерева все узлы,значение которых превышает вводимое пользователем число.Проблема с удалением из дерева узлов,которые по значению больше корня.
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
void del(int data,Tree *&root) { 
 if (root == NULL)
 return;
 
if(root->data >= data)
 while (root->data >= data)
 {
 Tree *sav = root;
 
 root = (root->left);
delete sav;
 sav = root;
 }
 
 
 else 
 while (root->data < data)
 {
 Tree *sav = root;
 
 root = (root->right);
 delete sav;
 sav = root;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 01:02     Деревья
Еще ссылки по теме:

Деревья - C++
нужно переписать программу с C++ на C #include &lt;string&gt; #include &lt;iostream&gt; #include &lt;sstream&gt; #include &lt;cassert&gt; enum...

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

Деревья - C++
Всем добрый день! Имеется такое задание : а) вставляет узел с записью Е в дерево, если ранее...

Б+ деревья - C++
Здравствуйте. Собственно недавно совсем столкнулся с проблемой по реализации Б+ дерева... имею код реализации Б дерева, но разница между Б...

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


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

Или воспользуйтесь поиском по форуму:
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.04.2013, 01:02     Деревья #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void del(node *&cur) { // удаление вершины из дерева.
    if (cur == NULL)
        return;
    if (cur->left == NULL || cur->right == NULL) {
        node *sav = cur;
        cur = (cur->left) ? cur->left : cur->right;
        delete sav;
        sav = NULL;
    } else {
        node** p = &cur->right;
        while ((*p)->left) p = &((*p)->left);
        cur->data = (*p)->data;
        del(*p);
    }
}
neske, хочу заметить что подобный алгоритм подходит не только к удалению корня/вершины, но таже подходит для удаления звена в целом.
Yandex
Объявления
04.04.2013, 01:02     Деревья
Ответ Создать тему
Опции темы

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