пожалуйста. помогите с программой
Задание 6. Деревья, упорядоченные графы без циклов
Из файла вводится в виде текстовой строки полином от нескольких переменных. Написать процедуры
- Построения представления полинома в виде дерева алгебраического выражения, внутренние вершины дерева кодируют операции «+» , «-» и «*», листья дерева имеют следующую структуру
- коэффициент ;
- указатель (переменная или константа)
- показатель степени переменной (для константы = 0)
- Обхода дерева (корень, левое поддерево, следующее дерево, …) с выводом информации в текстовый файл; (написать 2 варианта процедуры обхода дерева: рекурсивную процедуру, нерекурсивную процедуру)
- Вычисления значения полинома проходом по дереву (значения переменных задаются пользователем, продумать структуру дерева для организации эффективного алгоритма);
- Преобразовать дерево полинома в дерево другого полинома в котором все положительные константы уменьшены на одно и то же число.
- Реализовать с помощью деревьев операцию сложения двух полиномов
- Преобразования исходного кодового дерева в дерево полинома, получившегося из исходного путем умножения на переменную х.
- освобождения динамической памяти
Примечание: При выводе дерева в текстовый файл рекомендуется следующая расстановка вершин
Корневая вершина
Вершина 1 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 3 уровня
Вершина 1 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 1 уровня
и т.д.
Из файла вводится в виде текстовой строки полином от нескольких переменных. Написать процедуры
- Построения представления полинома в виде дерева алгебраического выражения, внутренние вершины дерева кодируют операции «+» , «-» и «*», листья дерева имеют следующую структуру
- коэффициент ;
- указатель (переменная или константа)
- показатель степени переменной (для константы = 0)
- Обхода дерева (корень, левое поддерево, следующее дерево, …) с выводом информации в текстовый файл; (написать 2 варианта процедуры обхода дерева: рекурсивную процедуру, нерекурсивную процедуру)
- Вычисления значения полинома проходом по дереву (значения переменных задаются пользователем, продумать структуру дерева для организации эффективного алгоритма);
- Преобразовать дерево полинома в дерево другого полинома в котором все положительные константы уменьшены на одно и то же число.
- Реализовать с помощью деревьев операцию сложения двух полиномов
- Преобразования исходного кодового дерева в дерево полинома, получившегося из исходного путем умножения на переменную х.
- освобождения динамической памяти
Примечание: При выводе дерева в текстовый файл рекомендуется следующая расстановка вершин
Корневая вершина
Вершина 1 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 3 уровня
Вершина 1 уровня
Вершина 2 уровня
Вершина 2 уровня
Вершина 1 уровня
и т.д.
вот струтура (хэдер)
#include "iostream"
#include "StdAfx.h"
struct tinfo
{
double coef;
int ukaz;
int step;
};
struct node
{
node tinfo;
node *right;
node *left;
};
void read_info (tinfo x);
tinfo write_info (int a, int b, int c);
void read_monom (ifstream in);
void write_monom (ifstream in);
#endif
#include "iostream"
#include "StdAfx.h"
struct tinfo
{
double coef;
int ukaz;
int step;
};
struct node
{
node tinfo;
node *right;
node *left;
};
void read_info (tinfo x);
tinfo write_info (int a, int b, int c);
void read_monom (ifstream in);
void write_monom (ifstream in);
#endif
void read_tinfo (tinfo x)//считывание числа из файла, вывод узла
{
if (x.ukaz == 0)
cout<<x.coef;
else
{
if (x.ukaz == 1)
{
if (x.step == 0)
cout<<x.coef;
else
cout<<"x("<<x.coef<<")^"<<x.step;
}
else
{
if (x.ukaz == 2)
{
if (x.coef == 0)
cout<<'*';
else
cout<<'+';
}
}
}
}
tinfo write_tinfo (int a, int b, int c)// записываем число (конкретно в одном узле)
{
tinfo x;
x.coef = a;
x.ukaz = b;
x.step = c;
}
{
if (x.ukaz == 0)
cout<<x.coef;
else
{
if (x.ukaz == 1)
{
if (x.step == 0)
cout<<x.coef;
else
cout<<"x("<<x.coef<<")^"<<x.step;
}
else
{
if (x.ukaz == 2)
{
if (x.coef == 0)
cout<<'*';
else
cout<<'+';
}
}
}
}
tinfo write_tinfo (int a, int b, int c)// записываем число (конкретно в одном узле)
{
tinfo x;
x.coef = a;
x.ukaz = b;
x.step = c;
}
помогите с методами обхода дерева, построения дерева (конструкторы) и т.п. все что связано с деревом
структуру узла продумал таким образом:
в узле хранится 3 цифры
сначала смотрим вторую цифру, если 0- то это коэффициент, если 1 - то это степень переменной, если 2- то это знак
далее подробнее:
если вторая цифра 0, то в первом и третьем поле можно хранить мусор, так как в них необходимости нет,
если вторая цифра 1, то далее смотрим на первую цифру - она показывает , при какой переменной она стоит (при первой , второй и т.д), затем смотрим 3ью цифру -
это уже значение степени переменной. например x^7 (как раз 7 хранится в третьй цифре;
если вторая цифра 2, то смторим на 1 ую цифру если 0. то это +, если 1 то *, на третью цифру не смотрим (можно хранить там мусор)
в узле хранится 3 цифры
сначала смотрим вторую цифру, если 0- то это коэффициент, если 1 - то это степень переменной, если 2- то это знак
далее подробнее:
если вторая цифра 0, то в первом и третьем поле можно хранить мусор, так как в них необходимости нет,
если вторая цифра 1, то далее смотрим на первую цифру - она показывает , при какой переменной она стоит (при первой , второй и т.д), затем смотрим 3ью цифру -
это уже значение степени переменной. например x^7 (как раз 7 хранится в третьй цифре;
если вторая цифра 2, то смторим на 1 ую цифру если 0. то это +, если 1 то *, на третью цифру не смотрим (можно хранить там мусор)
в узлах дерева 0 не храним
вот пример файла , откуда считываем:
1 2 3 4
1 0 0 0
3 2 0 3
полином будет выглядеть следующим образом:
1*x(1)^2*x(2)^3*x(3)^4+1+ 3*x(1)^2*x(3)^3
1 2 3 4
1 0 0 0
3 2 0 3
полином будет выглядеть следующим образом:
1*x(1)^2*x(2)^3*x(3)^4+1+ 3*x(1)^2*x(3)^3