Постройте и выведите на экран бинарное дерево. Найдите произведение элементов дерева, находящихся на уровне u

@mordol · Регистрация: 12.05.2015

Студворк — интернет-сервис помощи студентам

Я построил дерево вот код

C++

# include <iostream>
# include <conio.h>
#include <clocale>
using namespace std;
 
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Создали корень, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); /*Если аргумент а больше чем текущий элемент, кладем его вправо */
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u) 
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
void main ()
{   setlocale(LC_ALL,"RUS");
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout<<"введите количество элементов  ";
    cin>>n; //Вводим количество элементов
 
    for (int i=0;i<n;++i)
    {
    cout<<"ведите число  ";
    cin>>s; //Считываем элемент за элементом
   
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"наше дерево\n";
    print(tree,0);
    system("pause")`;       
}

Вот в чем проблема в какую часть кода нужно вставить цикл для вычисления произведения элементов дерева?

@Serg_o_Grey · 09.04.2016, 07:40

вам нужна глобальная переменная которая будет хранить произведение, и соответсвующее условие при обходе (что, мол, если мы находимся на уровне u, тогда умножаем его на глобальную переменную)

@mordol · 09.04.2016, 08:27 **[ТС]**

Сообщение от Serg_o_Grey

вам нужна глобальная переменная которая будет хранить произведение, и соответсвующее условие при обходе (что, мол, если мы находимся на уровне u, тогда умножаем его на глобальную переменную)

можете написать как строчка условия будет выглядеть в моем случае?

@Serg_o_Grey · 09.04.2016, 18:50

Кликните здесь для просмотра всего текста

C++

# include <iostream>
# include <conio.h>
using namespace std;
 
struct node
{
    int info;
    node *l, *r;
};
 
int x = 1;
node* tree = NULL;
node* first = NULL;
bool flag = true;
 
void push(node *t, node *f, int u, int h, int current_h);
void treeprint(node *t, int c, int u, int h);
void bypass(node *t, int c, int u);
void create_tree();
 
void push(node *t, node *f, int u, int h, int current_h)
{
    if (current_h < u)
    {
        if (current_h == u - 1)
        {
            if (flag == true)
            {
                if (t->l == NULL)
                {
                    t->l = new node;
                    t->l->l = NULL;
                    t->l->r = NULL;
                    cout << endl << "Введите очередное число: ";
                    cin >> t->l->info;
                    system("cls");
                    for (int i = 0; i <= u; i++) 
                    {
                        treeprint(f, 0, i, h);
                        cout << endl;
                    }
                    flag = false;
                }
                else
                {
                    if (t->r == NULL)
                    {
                        t->r = new node;
                        t->r->l = NULL;
                        t->r->r = NULL;
                        cout << endl << "Введите очередное число: ";
                        cin >> t->r->info;
                        system("cls");
                        for (int i = 0; i <= u; i++) 
                        {
                            treeprint(f, 0, i, h);
                            cout << endl;
                        }
                        flag = false;
                    }
                }
            }
        }
        else
        {
            if (t->l != NULL) push(t->l, f, u, h, current_h + 1);
            if (t->r != NULL) push(t->r, f, u, h, current_h + 1);
        }
    }
}
 
void treeprint(node *t, int c, int u, int h)    // c - счетчик глубины; u - уровень, которого нужно достичь; h - всего уровней
{
    int k = 0;
    if (c == u)
    {
        for (int i = h; i > c; i--) k = ((k + 1) * 2) - 1;
        for (int i = 0; i < k; i++) cout << "\t";
        cout << t->info << "\t";
        for (int i = 0; i <= k; i++) cout << "\t";
    }
    else
    {
        if (t->l != NULL) treeprint(t->l, c + 1, u, h);
        if (t->r != NULL) treeprint(t->r, c + 1, u, h);
    }
}
 
void bypass(node *t, int c, int u)
{
    if (c == u) x *= t->info;
    if (t->l != NULL) bypass(t->l, c + 1, u);
    if (t->r != NULL) bypass(t->r, c + 1, u);
}
 
void create_tree()
{
    int n;
    cout << "Введите кол-во элементов:  ";
        cin >> n;
    system("cls");
    int width = 1;
    int heigth = 0;
    for (int i = 0;;i++)
    {
        heigth += width;
        if (n <= heigth) {heigth = i; break;}
        else width *= 2;
    }
    tree = new node;
    tree->l = tree->r = NULL;
    cout << endl << "Введите первое число: ";
    cin >> tree->info;
    system("cls");
    treeprint(tree, 0, 0, heigth);
    cout << endl;
    first = tree;
    int k = 1;
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        flag = true;
        if (i > k) 
        {
            k = ((k+1) * 2) - 1;
            s++;
        }
        push(tree, first, s, heigth, 0);
    }
}
 
int main ()
{   
    setlocale(LC_ALL,"RUS");
    create_tree();
    bypass(tree, 0, 1);
    cout << endl  << "Произведение: " << x << endl;
    cin.get();
}

попробуйте сначала для 7 элементов (иначе не влезет в консоль дерево)

Добавлено через 3 минуты
ну или консоль увеличьте

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	09.04.2016, 07:40	2
	вам нужна глобальная переменная которая будет хранить произведение, и соответсвующее условие при обходе (что, мол, если мы находимся на уровне u, тогда умножаем его на глобальную переменную) 0

@mordol 1 / 1 / 2 Регистрация: 12.05.2015 Сообщений: 313
	09.04.2016, 08:27 [ТС]	3
	Сообщение от Serg_o_Grey вам нужна глобальная переменная которая будет хранить произведение, и соответсвующее условие при обходе (что, мол, если мы находимся на уровне u, тогда умножаем его на глобальную переменную) можете написать как строчка условия будет выглядеть в моем случае? 0

Опции темы

Постройте и выведите на экран бинарное дерево. Найдите произведение элементов дерева, находящихся на уровне u

Решение