Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
1

Деревья

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

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

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

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

Деревья
Всем добрый день! Имеется такое задание : а) вставляет...

14
14 / 14 / 4
Регистрация: 08.11.2010
Сообщений: 172
22.07.2012, 02:19 2
1.Не представляю как должна работать функция для удаления.
дерево обнули
0
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
22.07.2012, 02:29  [ТС] 3
Цитата Сообщение от rudeeeboy Посмотреть сообщение
1.Не представляю как должна работать функция для удаления.
дерево обнули
можно подробнее,пожалуйста?
0
5473 / 4868 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
22.07.2012, 06:11 4
Ошибки, которые на виду.
Цитата Сообщение от reznov Посмотреть сообщение
root=AddToTree(root,x);}
Функция у вас определена, как невозвращающая значение (void), хотя в ней (строка 18) присутствует некий return. Если присваиваете возвращаемое значение root, то функция должна возвращать значение типа *PNode.
0
187 / 180 / 25
Регистрация: 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();
}
1
5473 / 4868 / 831
Регистрация: 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;
}
1
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 07:26  [ТС] 7
Ребят,спасибо вам огромное!
Кто подскажет мне,что такое информационное поле дерева?
0
5473 / 4868 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
24.07.2012, 07:39 8
Цитата Сообщение от reznov Посмотреть сообщение
что такое информационное поле дерева?
В вашем коде это - int data;
0
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 17:39  [ТС] 9
Цитата Сообщение от nexen Посмотреть сообщение
Функция удаления узла имеешь ввиду? Она неоднозначна. У меня была такая задача в лабе по проге. Прикрепил её к сообщению. Собственно, DeleteNode - то, что тебе нужно
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
24.07.2012, 18:25 10
Цитата Сообщение от reznov Посмотреть сообщение
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
Почему же, можно, просто тогда я об этом не подумал, видимо. Или подумал, но не стал делать, так как из-за этого пришлось бы так же переписывать указатель на корень дерева.
Ошибка происходит из-за того, что я обращаются в потомкам parent-узла, коего корень не имеет, а посему parent == NULL.
0
1545 / 911 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
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);
    }
}
1
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;
}
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
25.07.2012, 07:57 13
Несколько не понял, что удаляется? (Нет возможности запустить сейчас и проверить)
Насколько я помню, в моей программе удаляться должно все корректно, если узел не корень, и удаление происходит только одного узла, а не поддерева, просто происходит перестройка дереве
0
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;
}
0
интересующийся
307 / 278 / 93
Регистрация: 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, хочу заметить что подобный алгоритм подходит не только к удалению корня/вершины, но таже подходит для удаления звена в целом.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.04.2013, 01:02

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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

Б деревья
Условие: текст программы вводится из файла.Используя бинарное дерево поиска выделить подсветкой...

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


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

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

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