С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Доронин_Виталий
0 / 0 / 0
Регистрация: 12.04.2014
Сообщений: 2
#1

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

02.05.2014, 14:52. Просмотров 270. Ответов 0
Метки нет (Все метки)

Условие задачи для создания программы:
"Создать класс 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)
Можно ли реализовать это как-то другим способом?
И ещё, можно ли реализовать удаление элемента дерева более коротким способом?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2014, 14:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Среднее геометрическое элементов бинарного дерева (C++):

Вычислить среднее арифметическое положительных элементов бинарного дерева - C++
Здравствуйте. Не могу реализовать функцию подсчета среднего арифметического положительных элементов в бинарном дереве. (Дерево, если что...

Вычислить среднее арифметическое положительных элементов бинарного дерева - C++
Здравствуйте. Не могу реализовать функцию подсчета вычисления среднего арифметического положительных элементов в бинарном дереве.(Дерево,...

Найти среднее арифметическое узлов бинарного дерева целых чисел - C++
Помогите решить. Надо срочно!!! Создать бинарное дерево целых чисел. Вывести на экран значение узлов и их среднее арифметическое

В массиве найти среднее геометрическое, все элементы с нечетными индексами уменьшить на среднее геометрическое - C++
В заданном массиве A1,A2, ... An найти среднее геометрическое, а затем все элементы с нечетными индексами уменьшить на величину среднего...

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

Вычислить среднее арифметическое и среднее геометрическое положительных элементов матрицы - C++
Составить функцию что вычесляет среднее арифметическое и среднее геометрическое положительных элементов матрицы.Помогите пожалуйста

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2014, 14:52
Привет! Вот еще темы с ответами:

Распределение элементов вектора внизу бинарного дерева - C++
Здравствуйте У меня такое задание : Дан вектор неопределенной длины (числа). Нужно сделать бинарное дерево, что бы самый нижний...

Функция подсчета четных элементов бинарного дерева - C++
Требуется написать функцию подсчета количества четных узлов бинарного дерева

Удаление элементов из бинарного дерева (не дерево поиска) - C++
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении согласных букв из дерева. проблема...

Метод адресирования элементов бинарного дерева. Что значит? - C++
Добрый вечер. В задании сказано построить структуру-бинарное дерево и т.д. И разработать метод адресирования элементов бинарного дерева....


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

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

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