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

Помогите переделать из двоичного дерева поиска, на бинарное идеально-сбалансированное дерево - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Входные/выходные данные. Метод решения и результат работы http://www.cyberforum.ru/cpp-beginners/thread1212159.html
#include <iostream> #include <cmath> using namespace std; int main() { char i; cin>>i; cout<<"Vvedite bukvu"<<endl; switch(i)
C++ Исправить void sort() Помогите исправить void sort() начало в 93 строке. ничего не записывает файл или как вообще можно отсортировать? Уже не знаю как сделать. #include <iostream> #include <conio.h> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <fstream> http://www.cyberforum.ru/cpp-beginners/thread1212153.html
приведение матрицы к итерационной форме C++
Здравствуйте. Подскажите, для чего нужен минус в формуле приведения недиагональных элементов матрицы к итерационному виду: C=-A/A;
C++ Составить и отладить программу редактор текстов
Составить и отладить программу редактор текстов со следующими обязательными операциями: - Вставка символа; - Перемещение / удаление / копирования блока; - Уничтожение символа; - Сохранение текущего файла. - Маркировка блока;
C++ Поиск в базе автомобилей по заданным параметрам http://www.cyberforum.ru/cpp-beginners/thread1212104.html
есть решенная задача - поиск больных в базе по заданным параметрам #include "stdafx.h" #include "stdio.h" #include "windows.h" #include "string.h" char * r(const char * txt){ char s;
C++ Может ли быть одинаковая хэш-сумма для разных наборов данных? Всем привет! Есть небольшая серия вопросов по хэшам, к ому не сложно, дайте свои комменты по вопросам. Просьба не засирать тему флудом :) 1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой? В данном вопросе не рассматриваем размерности данных и хеш сумм, а так же алгоритмы хеш сумм, чисто теория. 2. Если в п.1 такой вариант возможен, то нет... подробнее

Показать сообщение отдельно
demigod324
4 / 2 / 0
Регистрация: 17.03.2013
Сообщений: 102
19.06.2014, 12:37     Помогите переделать из двоичного дерева поиска, на бинарное идеально-сбалансированное дерево
У меня было такое задание:
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается:
- номер поезда;
- станция назначения;
- время отправления.
Данные в системе организовать в виде бинарного идеально-сбалансированного дерева.
Написать программу, которая:
- обеспечивает первоначальный ввод данных и формирование дерева;
- производит вывод всего дерева;
- осуществляет поиск поезда по номеру с использованием симметричного обхода дерева.

Сам код программы:
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
 
//---------------------------------------------------------------------------
 
#pragma argsused
struct traine                   //структура - дерево
{
    unsigned long time;
    unsigned short number;
    char *station;
    traine *left, *right;
};
//функция добавления элемента в дерево
traine* add(traine *beg, unsigned short number, unsigned long time, char station[50])
{
    if (!beg)   //если дерево пустое
    {
        traine *temp = new traine;
        temp -> number = number;
        temp -> time = time;
        temp -> station = new char[50];
        strcpy(temp -> station, station);
        temp -> left = 0;
        temp -> right = 0;
        return temp;
    }           //если дерево не пустое, начинается рекурсивный вход в него
    else if ((number) > (beg -> number))        //бОльшие номера идут в правое поддерево
    {
        beg -> right = add(beg -> right, number, time, station);
        return beg;
    }
    else                                        //меньшие номера идут в левое поддерево
    {
        beg -> left = add(beg -> left, number, time, station);
        return beg;
    }
}
 
//функция вывода всего дерева
void show_all(traine *temp, int vi)
{
    if (temp == NULL) return;
    else
    {
        show_all(temp -> right, ++vi);
        for (int i = 0; i < vi; ++i) cout << "/";
        cout << temp -> number << endl;
        vi--;
    }
    show_all(temp -> left, ++vi);
};
 
//поиск элемента с нужным номером, с учётом отсортированности дерева
void show_number(traine *temp, unsigned short number)
{
    unsigned long d, h, m, s, t;
    if (temp)
    {
        if (temp -> number < number) {show_number(temp -> right, number);}
        else if (temp -> number > number) {show_number(temp -> left, number);}
        else
        {
        t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;
        cout << "Nomer poezda:" << temp -> number << endl << "Vremia otpravri(d/h/m/s):" << d << ":" << h << ":" << m << ":" << s << endl << "Stancia:" << temp -> station << endl;
        return;
        }
    }
cout << "Takix zapiceu ne naudeno\n";
}
 
int main(int argc, char* argv[])
{
    char k;
    bool f;
    char strtmp[80];
    traine *list = 0;
    unsigned short d, h, m, s;
    unsigned short number;
    char station[30];
    do{
    cout << "Vvedite svou vibor:\n[1] Dodavit noviy zapis\n[2] Prosmotret vse zapisi\n[3] Prosmotret konkretniy nomer poezda\n[4] Vixod\n";
    do{
    cin >> k;
    
    if (k == '1'){
        do{
            cout << "Nomer poezda:\n";
            cin >> strtmp;
            number=atoi(strtmp);
        }while (!(number>0));
        do{
            cout << "Number of days:\n";
            cin >> strtmp;
            d=atoi(strtmp);
            cout << "Number of hours:\n";
            cin >> strtmp;
            h=atoi(strtmp);
            cout << "Number of minutes:\n";
            cin >> strtmp;
            m=atoi(strtmp);
            cout << "Number of seconds:\n";
            cin >> strtmp;
            s=atoi(strtmp);
        }while(d==0 && h==0 && m==0 && s==0);
        cout << "Nazvanie stancii:\n";
        cin >> station;
        list=add(list,number,s+m*60+h*3600+d*86400,station);
    }
 
    else if (k=='2'){
        if (list){
            show_all(list, 0);}
        else {cout << "Net poezda\n";}}
 
    else if (k=='3'){
        cout << "Vvedite nomer poezda:";
        do{
            cin >> strtmp;
            number=atoi(strtmp);
        }while (!(number>0));
        show_number(list,number);}
    }
    while (!((k=='3')||(k=='2')||(k=='1')||(k=='0')));
    }while (!(k=='0'));
    return 1;}
//---------------------------------------------------------------------------
Сделал правильно, но с использованием двоичного дерева поиска, помогите переделать на бинарное идеально-сбалансированное дерево.
Функция построения идеально-сбалансированного дерева:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Tree build (int n) {
         Tree NewTree;
         int nl, nr;
         if (n==0) build=0;  /*условие окончания рекурс. вызова*/
             else {
                         nl=int(n/2);
                         nr=n-nl-1;
                         Tree *New Tree= new Tree;
                         NewTree ->Elem=rand(30);
                         NewTree ->Left=build(nl);
                         NewTree ->Right=build(nr);
                      }
      return NewTree;
      }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 19:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru