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

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

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

Деревья - C++

22.07.2012, 02:13. Просмотров 978. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2012, 02:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Деревья (C++):

Деревья. - C++
Условие Найти и удалить (правым удалением), если существует, среднюю по значению из вершин дерева, у которых количество потомков в левом...

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
rudeeeboy
14 / 14 / 1
Регистрация: 08.11.2010
Сообщений: 172
22.07.2012, 02:19 #2
1.Не представляю как должна работать функция для удаления.
дерево обнули
0
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
22.07.2012, 02:29  [ТС] #3
Цитата Сообщение от rudeeeboy Посмотреть сообщение
1.Не представляю как должна работать функция для удаления.
дерево обнули
можно подробнее,пожалуйста?
0
alsav22
5420 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
22.07.2012, 06:11 #4
Ошибки, которые на виду.
Цитата Сообщение от reznov Посмотреть сообщение
root=AddToTree(root,x);}
Функция у вас определена, как невозвращающая значение (void), хотя в ней (строка 18) присутствует некий return. Если присваиваете возвращаемое значение root, то функция должна возвращать значение типа *PNode.
0
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();
}
1
alsav22
5420 / 4816 / 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;
}
1
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 07:26  [ТС] #7
Ребят,спасибо вам огромное!
Кто подскажет мне,что такое информационное поле дерева?
0
alsav22
5420 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
24.07.2012, 07:39 #8
Цитата Сообщение от reznov Посмотреть сообщение
что такое информационное поле дерева?
В вашем коде это - int data;
0
reznov
0 / 0 / 0
Регистрация: 21.07.2012
Сообщений: 6
24.07.2012, 17:39  [ТС] #9
Цитата Сообщение от nexen Посмотреть сообщение
Функция удаления узла имеешь ввиду? Она неоднозначна. У меня была такая задача в лабе по проге. Прикрепил её к сообщению. Собственно, DeleteNode - то, что тебе нужно
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
24.07.2012, 18:25 #10
Цитата Сообщение от reznov Посмотреть сообщение
Если вводимое число равно корню дерева,программа выдаёт ошибку...видимо нельзя удалить корень дерева.
Почему же, можно, просто тогда я об этом не подумал, видимо. Или подумал, но не стал делать, так как из-за этого пришлось бы так же переписывать указатель на корень дерева.
Ошибка происходит из-за того, что я обращаются в потомкам parent-узла, коего корень не имеет, а посему parent == NULL.
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
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
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;
}
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
25.07.2012, 07:57 #13
Несколько не понял, что удаляется? (Нет возможности запустить сейчас и проверить)
Насколько я помню, в моей программе удаляться должно все корректно, если узел не корень, и удаление происходит только одного узла, а не поддерева, просто происходит перестройка дереве
0
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;
}
0
xtorne21st
интересующийся
304 / 275 / 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, хочу заметить что подобный алгоритм подходит не только к удалению корня/вершины, но таже подходит для удаления звена в целом.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 01:02
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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