Найти 3 узла дерева, сумма которых равна корневому узлу - C++ - Ответ 9303016

@no_justice · Регистрация: 22.06.2016

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

Здравствуйте! Срочно! Необходимо запилить функцию нахождения любых трех узлов(включая листья), сумма ключей которых равна значению ключа корня.
Код ниже:

C++

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
 
#include <iostream>
#include <conio.h>
#include <cstdio>
#include <Windows.h>
#include <string>
#include <iomanip>
#include <fstream>
using namespace std;
struct rasp
{
    string firstname;
    string lastname;
    string fathersname;
    unsigned int originYear;
    unsigned int height;
    unsigned int weight;
    string blood;
 
};
struct Tree
{
    rasp specie;
    Tree *l, *r;
};
typedef void(*f)(Tree *, Tree **);
void Insert(Tree *fill, Tree **Root);
void read_file(Tree **Root, bool &isEmpty, int &count, f Insert);
void print(Tree *&t, int level);
void Del_All(Tree *t);
void menu_admin(int &button);
Tree* Del(Tree *Root, int key);
void Input(Tree **Root, bool &isEmpty, int &count);
void Search(Tree *Root, bool &isEmpty);
int countnodes(Tree *&t);
void dopzad(Tree *&t, Tree *&Root);
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int count = 0, button = -1;
    bool isEmpty = true;
    Tree *Root = NULL;
    read_file(&Root, isEmpty, count, Insert);
    while (button)
    {
        system("cls");
        menu_admin(button);
        switch (button) {
        case 1: {
            Input(&Root, isEmpty, count);
            break;
        }
        case 2:
        {
            print(Root, 0);
            system("pause");
            break;
        }
        case 3: {
            int key;
            cout << "Введите ключ:";
            cin >> key;
            Root = Del(Root, key);
            system("pause");
            break;
        }
        case 4: {
            Search(Root, isEmpty);
            system("pause");
            break;
        }
        case 5: {
            int counter = 0;
            Tree *left = Root->l;
            cout << countnodes(left);
            
            system("pause");
            break;
        }
        case 6: {
            
            
 
            system("pause");
            break;
        }
        }
    }
    Del_All(Root);
    system("pause");
    return 0;
}
void read_file(Tree **Root, bool &isEmpty, int &count, f Insert)
{
    string buff;
 
    ifstream fin;
 
 
    Tree *fill = new Tree;
 
    fin.open("base.txt");
    if (!fin.is_open())
    {
        cout << "Ошибка работы с базой данных! Выход" << endl;
        system("pause");
 
        return;
    }
    else {
 
        while (fin >> fill->specie.firstname >> fill->specie.lastname >> fill->specie.fathersname >> fill->specie.blood >> fill->specie.height >> fill->specie.weight >> fill->specie.originYear)
        {
            isEmpty = false;
            Insert(fill, *&Root);
            count++;
        }
        cout << "База успешно считана!" << endl;
        system("pause");
        system("cls");
    }
}
void Insert(Tree *fill, Tree **Root)
{
    Tree *temp = *Root;
    Tree *form = new Tree;
 
    form->specie.firstname = fill->specie.firstname;
    form->specie.lastname = fill->specie.lastname;
    form->specie.fathersname = fill->specie.fathersname;
    form->specie.blood = fill->specie.blood;
    form->specie.weight = fill->specie.weight;
    form->specie.height = fill->specie.height;
    form->specie.originYear = fill->specie.originYear;
 
    form->l = NULL;
    form->r = NULL;
 
    if (temp == NULL)
    {
 
        *Root = form;
 
        return;
    }
    
        
    while (1)
    {
        if (temp->specie.originYear >= form->specie.originYear)
        {
 
            if (temp->l)
                temp = temp->l;
            else { temp->l = form; break; }
        }
        else {
            if (temp->r)
                temp = temp->r;
            else {
                temp->r = form; break;
            }
        }
 
 
    }
}
void menu_admin(int &button)
{
    cout << "|----------------------|" << endl;
    cout << "|*********Меню*********|" << endl;
    cout << "|----------------------|" << endl;
    cout << "|Введите номер действия|" << endl;
    cout << "|----------------------|" << endl;
    cout << "|1. Ввести запись      |" << endl;
    cout << "|2. Вывести все записи |" << endl;
    cout << "|3. Удалить запись     |" << endl;
    cout << "|   по ключу           |" << endl;
    cout << "|4. Поиск по ключу     |" << endl;
    cout << "|5. Задание варианта   |" << endl;
    cout << "|6. Задание доп        |" << endl;
    cout << "|0. Выйти из программы |" << endl;
    cout << "|~~~~~~~~~~~~~~~~~~~~~~|" << endl;
 
    cout << "\nВведите команду:";
    cin >> button;
    if (button < 0 || button >6)
    {
        cout << "Неверная команда!" << endl;
        cin.clear();
        while (cin.get() != '\n');
        system("pause");
        return;
    }
}
void Search(Tree *Root, bool &isEmpty)
{
    if (isEmpty)
    {
        cout << "Список пуст! Поиск невозможен!" << endl;
        system("pause");
        return;
    }
    Tree *print = Root;
    unsigned int year;
    cout << "Введите год(ключ поиска):";
    cin >> year;
    while (year > 2017 || year < 0)
    {
        cout << "Неверный год!" << endl;
        cin.clear();
        while (cin.get() != '\n');
        system("pause");
        system("cls");
        cout << "Введите год(ключ поиска):";
        cin >> year;
    }
 
 
 
    while (print != NULL && print->specie.originYear != year) {
        if (print->specie.originYear > year)  print = print->l;
        else print = print->r;
    }
 
 
    system("cls");
    cout << "__________________________________________________________________" << endl;
    cout << "|  №|   Фамилия      Имя     Отчество  |Гр. кр.|Рост|Вес|Год рож-я|" << endl;
    if (print != NULL)
    {
 
        cout << "|" << setw(3) << "1" << "|" << setw(14) << print->specie.firstname << setw(7) << print->specie.lastname << setw(13) << print->specie.fathersname << "|" << setw(7) << print->specie.blood << "|" << setw(4) << print->specie.height << "|" << setw(3) << print->specie.weight << "|" << setw(9) << print->specie.originYear << "|" << endl;
        cout << "|___|__________________________________|_______|____|___|_________|" << endl;
 
    }
 
}
void print(Tree *&t, int level)
{
    if (t == NULL) return;
    else
    {
        print(t->l, ++level);
        for (int i = 0; i<level; ++i) cout << "  ";
        cout
            << t->specie.originYear << endl;
        level--;
    }
    print(t->r, ++level);
}
Tree* Del(Tree *Root, int key) {
    Tree *Del, *Prev_Del, *R, *Prev_R;
 
    Del = Root;
    Prev_Del = NULL;
 
    while (Del != NULL && Del->specie.originYear != key) {
        Prev_Del = Del;
        if (Del->specie.originYear> key)  Del = Del->l;
        else Del = Del->r;
    }
    if (Del == NULL) {
        puts("\n Нет записи по заданному ключу!");
        return Root;
    }
 
    if (Del->r == NULL) R = Del->l;
    else
        if (Del->l == NULL) R = Del->r;
        else {
 
            Prev_R = Del;
            R = Del->l;
            while (R->r != NULL) {
                Prev_R = R;
                R = R->r;
            }
 
            if (Prev_R == Del)
                R->r = Del->r;
            else {
                R->r = Del->r;
                Prev_R->r = R->l;
                R->l = Prev_R;
            }
        }
        if (Del == Root) Root = R;
        else
 
            if (Del->specie.originYear< Prev_Del->specie.originYear)  Prev_Del->l = R;
            else    Prev_Del->r = R;
            printf("\n Удалена запись по ключу  %d \n", Del->specie.originYear);
            
            free(Del);
            return Root;
}
 
void dopzad(Tree *&t, Tree *&Root)
{
 
    system("pause");
}
 
 
 
int countnodes(Tree *&t)
{
    if (t->l == NULL && t->r == NULL)
        return 1;
    int left, right;
    if (t->l != NULL)
        left = countnodes(t->l);
    else left = 0;
    if (t->r != NULL)
        right = countnodes(t->r);
    else right = 0;
    return left + right+1;
}
 
void Input(Tree **Root, bool &isEmpty, int &count)
{
 
    Tree *temp = *Root;
    Tree *form = new Tree;
 
    cout << "Введите фамилию: ";
    cin.ignore();
 
    cin >> form->specie.firstname;
    cout << "Введите имя(Инициал(пример - Богдан = "Б."): ";
    cin.ignore();
    cin >> form->specie.lastname;
    while (form->specie.lastname.length() > 5)
    {
        system("cls");
        cout << "Ошибка! Введите данные корректно." << endl;
        cin.clear();
        while (cin.get() != '\n');
        cout << "Введите имя(Инициал(пример - Богдан = "Б."): ";
        cin >> form->specie.lastname;
    }
 
    cout << "Введите отчество(Инициал(пример - Николаевич = "Н."): ";
    cin.ignore();
    cin >> form->specie.fathersname;
    while (form->specie.fathersname.length() > 5)
    {
        system("cls");
        cout << "Ошибка! Введите данные корректно." << endl;
        cin.clear();
        while (cin.get() != '\n');
        cout << "Введите отчество(Инициал(пример - Николаевич = "Н."): ";
        cin >> form->specie.fathersname;
    }
 
    cout << "\nВведите группу крови: ";
    cin >> form->specie.blood;
    while (form->specie.blood.length() > 5)
    {
        system("cls");
        cout << "Ошибка! Введите данные корректно." << endl;
        cin.clear();
        while (cin.get() != '\n');
        cout << "\nВведите группу крови: ";
        cin >> form->specie.blood;
    }
 
    cout << "\nВведите рост(40-300, в см.): ";
    cin >> (form)->specie.height;
    while (form->specie.height > 300 || form->specie.height < 40) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "\nВведите рост(40-300, в см.): ";
        cin >> (form)->specie.height;
    }
 
    cout << "\nВведите вес(0-300, в кг.): ";
    cin >> (form)->specie.weight;
    while (form->specie.weight > 300 || form->specie.weight < 0) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "\nВведите вес(0-300, в кг.): ";
        cin >> (form)->specie.weight;
    }
 
    cout << "\nВведите год рождения(1900-2100): ";
    cin >> (form)->specie.originYear;
    while (form->specie.originYear >2100 || form->specie.originYear < 1900) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "\nВведите год рождения(1900-2100): ";
        cin >> (form)->specie.originYear;
    }
    form->l = NULL;
    form->r = NULL;
    if (temp == NULL)
    {
        *Root = form;
        count++;
        isEmpty = false;
        return;
    }
    if (form->specie.originYear < temp->specie.originYear)
        
    while (1)
    {
        if (temp->specie.originYear >= form->specie.originYear)
        {
            if (temp->l)
                temp = temp->l;
            else { temp->l = form; break; }
        }
        else {
            if (temp->r)
                temp = temp->r;
            else {
                temp->r = form; break;
            }
        }
    }
    count++;
    isEmpty = false;
}
void Del_All(Tree *t) {
    if (t != NULL) {
        Del_All(t->l);
        Del_All(t->r);
        free(t);
    }
}

Ключ дерева - год рождения. Сделать отдельной функцией. Буду благодарен за наводку и помощь в решении! Спасибо!

Вернуться к обсуждению:
Найти 3 узла дерева, сумма которых равна корневому узлу C++

Другие темы раздела
C++ Реализовать базовый класс Array Здравствуйте. Очень нужна ваша помощь с заданием: Создать базовый класс Array с полями: массив типа unsigned char и поле для хранения количества элементов у текущего объекта-массива. Максимально возможный размер массива задается статистической константой.реализуйте конструктор инициализации, задающий количество элементов и начальное значение (по умолчанию 0). Реализуйте методы доступа к... https://www.cyberforum.ru/ cpp-beginners/ thread1768876.html	C++ Поиск в двоичном дереве Добрый день. Нужно построить англо-русский словарь как двоичное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Дальше нужно сформировать новое представление словаря в виде двоичного дерева по следующему алгоритму: а) в старом словаре ищется компонента с наибольшим значением счетчика обращений; б)...
C++ Вычислить значение суммы используя оператор for https://www.cyberforum.ru/ cpp-beginners/ thread1768847.html S= \sum \sum_{10}^{i=-10}1/i^3 i\neq 0 Помогите пожалуйста S= \sum_{10}^{i=-10}1/i^3 i\neq 0	C++ Гаражная стоянка https://www.cyberforum.ru/ cpp-beginners/ thread1768843.html Условие задачи: Гаражная стоянка имеет одну стояночную полосу, причем единственный въезд и единственный выезд находятся в одном конце полосы. Если владелец автомашины приходит забрать свой автомобиль, который не является ближайшим к выходу, то все автомашины, загораживающие проезд, удаляются, машина данного владельца выводится со стоянки, а другие машины возвращаются на стоянку в исходном...
Структура «Автобусный тур» C++ Структура «Автобусный тур» с полями «пункт назначения», «дата начала тура», «дата окончания тура», «количество человек в группе». Функция - расчёт количества автобусов (42 места), необходимых для перевозки группы. Мне нужно сделать типа как вот эта программа по такому же образу int f(int p,string k) { int l; if(k=="1"){ l=150*p; }	C++ Разряженный вектор произвольной длины Помогите пожалуйста ответить на вопрос:"Определить набор операций и структуру данных для абстрактного типа данных «Разряженный вектор произвольной длины»". https://www.cyberforum.ru/ cpp-beginners/ thread1768808.html
C++ Структуры: отобразить на экран анкетные данные студентов-отличников в виде таблицы https://www.cyberforum.ru/ cpp-beginners/ thread1768805.html Помогите разобраться как написать программу,вообще не понимаю алгоритм действий и как составить программу( Дан список учебной группы, включающий 20 человек. Для каждого студента известны: фамилия, имя, дата рождения, оценки по всем дисциплинам за последний семестр. Составить программу, которая обеспечивает ввод информации и отображение ее на экран в виде таблицы. ...	Игра "Калах" C++ Для выбора лунки, с которой делается очередной ход должны использоваться клавиши "←", "→". Ход определяется нажатием клавиши "SPACE". При нажати клавиши "н" на экран должны выводиться правила игры. Перед началом игры должны запрашиваться имена игроков. Как это можно реализовать? Правила игры: https://ru.wikipedia.org/wiki/Калах#.D0.9F.D1.80.D0.B0.D0.B2.D0.B8.D0.BB.D0.B0
C++ Ошибка при быстрой сортировке файла: "string subscript out of range" В файле input.txt содержатся сведения о группе студентов в формате: номер группы; запись о каждом студенте группы содержит следующие сведения: фамилия, имя, отчество, год рождения, оценки по пяти предметам. в алфавитном порядке по фамилии методом «быстрой»; #include <iostream> #include <fstream> #include <string> https://www.cyberforum.ru/ cpp-beginners/ thread1768780.html	C++ Цикл не делает последнюю итерацию https://www.cyberforum.ru/ cpp-beginners/ thread1768751.html for(x=1;x<=4;x+=0.2) { cout<<x<<endl; } Почему последнее число которое выводит это 3.8, а не 4?
Неправильный результат при возведении числа в степень C++ #include<stdio.h> #include<math.h> main() { int n,a; scanf("%d",&n); a=pow(2,n); printf("%d",a); }	C++ Queue и пользовательский класс Недавно начал изучать STL, хотел поработать с queue. Можно ли очередь с типом, который я создал сам? Например class Simple { int a; int b; }; int main() { queue<Simple> q1; } https://www.cyberforum.ru/ cpp-beginners/ thread1768730.html

	22.06.2016, 19:10