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

Среднее геометрическое элементов бинарного дерева - C++

Восстановить пароль Регистрация
 
Доронин_Виталий
0 / 0 / 0
Регистрация: 12.04.2014
Сообщений: 2
02.05.2014, 14:52     Среднее геометрическое элементов бинарного дерева #1
Условие задачи для создания программы:
"Создать класс TreeDouble, для работы с элементами бинарного дерева вещественных чисел.
В этом классе должны быть определены функции-члены класса, обеспечивающие: заполнение дерева, добавление элементов дерева, удаление элемента дерева.
Дополнительно перезагрузить в этом классе операторные функции, которые обеспечивают ввод/вывод элементов класса (в том числе и в алфавитном порядке).
Так-же нужно определить операторную функцию / , которая возвращает среднее геометрическое всех элементов дерева."


classes.h
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
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <fstream>
using namespace std;
 
struct TreeNode
{
    friend class Tree; /* Основной класс должен быть объявлен дружественным, чтобы он имел доступ к элементам узла */  
    // Элементы данных:
    double data;
    TreeNode* lPtr;
    TreeNode* rPtr;
    TreeNode* parent;
    public:
    // Конструктор:
    TreeNode(double d)
    {data = d; lPtr = 0; rPtr = 0; parent=0;}
};
// Основной класс:
class Tree
{
private:
    TreeNode* rootPtr; // указатель на корневой узел (элемент данных)
    // закрытые функции:
    void Add(TreeNode*, TreeNode*&,double); // добавляет новый элемент
    void preOrder(TreeNode*);  // Обход в ширину
    void inOrder(TreeNode*); // Последовательный обход
    void postOrder(TreeNode*); // Обратный обход
    void sum1(TreeNode*); // Функция, для нахождения суммы всех элементов и подсчета их числа
    Tree* operator - (TreeNode* ptr); //  операторная функцию, которая возвращает среднее геометрическое всех элементов дерева.
    int s; // счетчик элементов
    double sum,cc; //переменные для хранения суммы элементов и среднего геометрического     
public:
    // Конструктор:
    Tree() {rootPtr = 0; s=0; sum=0;cc=0;}
    // открытые функции, которые будет использовать главная программа:  
    void Add(double);   
    void Del(double); //удаляет узел дерева
    void preOrder();
    void inOrder();
    void postOrder();
    void FillTreeNode(TreeNode*); // Заполнение ветви и её дочерних ветвей случайными числами
    void FillTree(); // Заполнение элементов дерева
    void sum1();
    void gsum();
    Tree* operator - ();    
};
classes.cpp
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <fstream>
#include <math.h>
#include "classes.h"
using namespace std;
// Определение функций:
// Функция, которая добавляет узел к дереву:
void Tree :: Add(double m)
{
    Add(NULL, rootPtr, m);
/* Здесь и далее перегрузка функций требуется, поскольку главная программа не имеет доступа к корневому узлу дерева, поэтому единственное назначение этого вызова функции Add() – передать адрес корневого узла. */
}
/* Основная функция, которая обходит дерево и привязывает новый узел к дереву: */
void Tree :: Add(TreeNode* parent, TreeNode*& ptr, double m)
{
    if (!ptr) 
    {
/* Если текущий указатель равен 0, к нему подвязываем новый узел
 или создаем корневой */
 
        // Определяем, если у корня дерева нет потомков, то неважно какой родитель передан, для нормального функционирования дерева, необходимо, чтобы корень был действительно корнем и принудительно изменяем переданного родителя ветки, на ссылку корня
        
        ptr = new TreeNode(m);
        ptr->parent=parent;
    }
/* благодаря тому, что параметр ptr объявлен как ссылка на указатель, устанавливается значение указателя на корневой узел или изменяется значение указателя в том узле, к которому привязывается новый */
    else
    {
        if (m < ptr->data) Add(ptr, ptr->lPtr, m); 
// если новый элемент меньше значения в текущем узле, идем налево 
        else if (m > ptr->data) Add(ptr, ptr->rPtr, m);
// в противном случае - направо
// если встречается повторяющееся значение, то оно  игнорируется, благодаря этому все элементы дерева будут различны 
    }
}
/* три нижеследующие функции отличаются только последовательностью выполнения операторов и благодаря этому позволяют выводить элементы дерева на экран в различном порядке */ 
void Tree :: preOrder()
{
    preOrder(rootPtr);
}
void Tree :: preOrder(TreeNode* ptr)
{
    if (ptr)
    {
        cout << ptr->data << " "; // выводим элемент
        preOrder(ptr->lPtr); // спускаемся влево
        preOrder(ptr->rPtr); // спускаемся вправо
    }
}
// Последовательный обход
void Tree :: inOrder()
{
    inOrder(rootPtr);
}
// обход в порядке возрастания:
void Tree :: inOrder(TreeNode* ptr)
{
    if (ptr)
    {
        inOrder(ptr->lPtr);
        cout << ptr->data << " ";
        inOrder(ptr->rPtr);
    }
}
// Обход в обратном направлении:
void Tree :: postOrder()
{ 
    postOrder(rootPtr);
}
void Tree :: postOrder(TreeNode* ptr)
{
    if (ptr)
    {
        postOrder(ptr->lPtr);
        postOrder(ptr->rPtr);
        cout << ptr->data << " ";
    }
}
void Tree::FillTreeNode(TreeNode* ptr)
{
    if (ptr)
    {
        FillTreeNode(ptr->lPtr);
        FillTreeNode(ptr->rPtr);
 
        // Заполняем данные ветки случайным числом
        ptr->data=rand()%25+'A';
    }
}
void Tree::FillTree()
{
    if (rootPtr)
    {
        FillTreeNode(rootPtr);
    }
}
void Tree::sum1()
{
    sum1(rootPtr);
}
void Tree :: sum1(TreeNode* ptr)
{
    if (ptr)
    {
        sum1(ptr->lPtr);
        sum1(ptr->rPtr);
        sum+=ptr->data;
        s++;    
    }   
}
void Tree::gsum()
{   
    cc=pow(sum,1./s);
    cout<<"Геометрическая сумма всех членов дерева:  "<<cc<<endl;
    s=0; sum=0; cc=0;   
}
Tree* Tree::operator -(TreeNode* ptr)
{
    return 0;
}
Tree* Tree::operator -()
{
 
    s=0; cc=0; sum=0;
    sum1();
    gsum();
    return this;
}
void Tree::Del(double data)
{
    TreeNode * pointer = rootPtr;
    TreeNode * parent  = NULL;
 
    while (pointer != NULL && pointer->data != data)
    {
        parent = pointer;
        if (data < pointer->data)
            pointer = pointer->lPtr;
        else
            pointer = pointer->rPtr;
    }
 
    if (pointer != NULL)
    {
        TreeNode * removed = NULL;
 
        if (pointer->lPtr == NULL || pointer->rPtr == NULL)
        {   
            TreeNode * child = NULL;
            removed = pointer;
 
            if (pointer->lPtr != NULL)
                child = pointer->lPtr;
            else if (pointer->rPtr != NULL)
                child = pointer->rPtr;
 
            if (parent == NULL)
                rootPtr = child;
            else
            {
                if (parent->lPtr == pointer)
                    parent->lPtr = child;
                else
                    parent->rPtr = child;
            }
        }
        else // (pointer->left != NULL && pointer->right != NULL)
        {
            TreeNode * mostLeft = pointer->rPtr;
            TreeNode * mostLeftParent = pointer;
            
            while (mostLeft->lPtr != NULL)
            {
                mostLeftParent = mostLeft;
                mostLeft = mostLeft->lPtr;
            }
 
            pointer->data = mostLeft->data;
            removed = mostLeft;
 
            if (mostLeftParent->lPtr == mostLeft)
                mostLeftParent->lPtr = NULL;
            else
                mostLeftParent->rPtr = NULL;
        }
        delete removed;
    }
}
main.cpp
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
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <fstream>
#include "classes.h"
using namespace std;
 
// Пример использования класса:
int main()
{
    //Настройки шрифтов и региональных стандартов: 
    if(SetConsoleCP(1251)==0)
    //проверка правильности установки кодировки символов для ввода
    {
        cerr<<"Fialed to set codepage!"<<endl;
    }
    if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
    {
        cerr<<"Failed to set OUTPUT page!"<<endl;
    }
    
        Tree tree1;
        cout <<"Пустая последовательность: \n";
        tree1.inOrder();
        cout <<"tree1.Add(...) \n";
        tree1.Add(1);       
        tree1.Add(3);
        tree1.Add(2);           
        tree1.Add(5);
        tree1.Add(4);
        tree1.Add(6);
    
        cout <<"Отсортированная последовательность: \n";
        tree1.inOrder();
        cout<<endl;
 
        cout <<"tree1.Del(3) \n";
        tree1.Del(3);
 
        cout <<"Отсортированная последовательность: \n";
        tree1.inOrder();
        cout<<endl;
        -tree1;
                cout<<endl<<"Заполнение веток дерева случайными числами: "<<endl;
        tree.FillTree();
        tree.inOrder();
        cout<<endl<<endl;
    _getch();
    return 0;
}
Программа работает и считает всё правильно..но есть вопрос, по поводу этих строчек:
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
void Tree::sum1()
{
    sum1(rootPtr);
} 
 
void Tree :: sum1(TreeNode* ptr)
{
    if (ptr)
    {
        sum1(ptr->lPtr);
        sum1(ptr->rPtr);
        sum+=ptr->data;
        s++;    
    }   
} 
 
void Tree::gsum()
{
    cc=pow(sum,1./s);
    cout<<"Геометрическая сумма всех членов дерева:  "<<cc<<endl;
    s=0; sum=0; cc=0;   
} 
 
Tree* Tree::operator -(TreeNode* ptr)
{
    return 0;
} 
 
Tree* Tree::operator -()
{ 
    s=0; cc=0; sum=0;
    sum1();
    gsum();
    return this;
}
Я в теории не силен и писал методом проб и ошибок. Эти строчки буквально подобрал. Но преподаватель говорит, что таким образом нельзя осуществить перегрузку операторной функции и нужно сделать это другим способом. По его мнению, запись
C++
1
2
3
4
Tree* Tree::operator -(TreeNode* ptr)
{
    return 0;
}
здесь вообще не нужна, но без неё программа выводит ошибку в строке 43(main.cpp)
Можно ли реализовать это как-то другим способом?
И ещё, можно ли реализовать удаление элемента дерева более коротким способом?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2014, 14:52     Среднее геометрическое элементов бинарного дерева
Посмотрите здесь:

Найти среднее геометрическое элементов массива A C++
среднее геометрическое положительных элементов C++
Вычислить среднее арифметическое и среднее геометрическое положительных элементов матрицы C++
C++ Найти среднее арифметическое узлов бинарного дерева целых чисел
В массиве найти среднее геометрическое, все элементы с нечетными индексами уменьшить на среднее геометрическое C++
Найти среднее геометрическое и среднее арифметическое элементов главной диагонали матрицы C++
C++ Удаление элементов из бинарного дерева (не дерево поиска)
Функция подсчета четных элементов бинарного дерева C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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