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

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

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

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

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

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

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

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

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

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

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Реализовать структуру данных «сбалансированное дерево поиска» - C++
Добрый вечер. Дали задание, не до конца ясна реализация, не могли бы подбросить пару шаблонов, или готовых решений, чтобы посмотреть на...

Дерево двоичного поиска - C++
Помогите реализовать дерево двоичного поиска (операции добавления данных, прямого обхода с печатью ключей). Буду ооооочень благодарен ...

Бинарное Дерево(обход дерева) - C++
добрый вечер всем!) в универе задали написать бинарное дерево со всеми видами обхода и т.п. я их написал.. но еще дали 1 вывод его надо...


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

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

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