Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
demigod324
4 / 2 / 0
Регистрация: 17.03.2013
Сообщений: 103
#1

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

19.06.2014, 12:37. Просмотров 233. Ответов 0
Метки нет (Все метки)

У меня было такое задание:
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается:
- номер поезда;
- станция назначения;
- время отправления.
Данные в системе организовать в виде бинарного идеально-сбалансированного дерева.
Написать программу, которая:
- обеспечивает первоначальный ввод данных и формирование дерева;
- производит вывод всего дерева;
- осуществляет поиск поезда по номеру с использованием симметричного обхода дерева.

Сам код программы:
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;
      }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2014, 12:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите переделать из двоичного дерева поиска, на бинарное идеально-сбалансированное дерево (C++):

Сформировать идеально сбалансированное бинарное дерево - C++
Дан текст программы. Проверти правильно или нет описание сделал? TNode* makePerfectBalancedTree(int n, TNode* p) // происходит...

Сформировать идеально сбалансированное бинарное дерево и найти в нем максимальный элемент - C++
Далее преобразовать его в дерево поиска и тоже найти максимальный элемент.

Идеально сбалансированное дерево - C++
В файле input.txt хранится последовательность целых чисел.По входной последовательности построить идеально сбалансированное дерево и найти...

Идеально сбалансированное дерево - C++
Всем привет. Нужно построить идеально сбалансированное дерево из букв, упорядоченное я сделал, но не могу понять, как сделать идеально...

Идеально сбалансированное дерево - C++
Интересует как работает этот кусок кода) по идеи Create(&amp;tmp-&gt;right, nr); сюда компилятор никогда не доберется? и еще как она выходит из...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2014, 12:37
Привет! Вот еще темы с ответами:

Сбалансированное не бинарное дерево - C++
Каково определение сбалансированного произвольного, не бинарного дерева ? Например, для бинарного говориться, что расхождение высот...

Сбалансированное дерево (бинарное) - C++
кто сможет, пожалуйста напишите код с++, построения сбалансированного дерева,функцию добавления элемента в дерево и восстановелния...

Сбалансированное бинарное дерево. Структуры даннных - C++
Доброе время суток,уважаемые посетители форума! Задали на структурах данных создать сбалансированное бин. дерево,после чего построить из...

Сбалансированное двоичное дерево поиска - C++
ЗДРАВСТВУЙТЕ! Есть код. При компилировании выдаёт ошибку. Помогите исправить пожалуйста. avl.h #include &lt;iostream&gt; #include...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.