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

Деревья - C++

Восстановить пароль Регистрация
 
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
22.07.2012, 02:13     Деревья #1
Я не особо разбираюсь в программировании (т.к это не связано с моей будущей специальностью,но те кто составлял учебный курс так не считают )поэтому не бросайтесь камнями.
Суть задания:
"Информационное поле двоичного упорядоченного дерева содержит целое число.Удалить из дерева все узлы,информационное поле которых превышает некоторое вводимое пользователем число."
У меня возникли некоторые сложности:
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++
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
5282 / 4801 / 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
5282 / 4801 / 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
5282 / 4801 / 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
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,689
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++

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

Или воспользуйтесь поиском по форуму:
xtorne21st
интересующийся
300 / 271 / 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     Деревья
Ответ Создать тему
Опции темы

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