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

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

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

Сам код программы:
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;
      }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2014, 12:37     Помогите переделать из двоичного дерева поиска, на бинарное идеально-сбалансированное дерево
Посмотрите здесь:

C++ Сбалансированное дерево (бинарное)
C++ Сбалансированное двоичное дерево поиска
C++ Сформировать идеально сбалансированное бинарное дерево
Идеально сбалансированное дерево C++
Идеально сбалансированное дерево C++
C++ Реализовать структуру данных «сбалансированное дерево поиска»
Сбалансированное бинарное дерево. Структуры даннных C++
Идеально сбалансированное дерево C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 15:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru