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

Из списка в двоичное дерево - C++

Восстановить пароль Регистрация
 
Julia9311
3 / 3 / 0
Регистрация: 05.11.2011
Сообщений: 190
11.06.2012, 17:32     Из списка в двоичное дерево #1
Эта программа, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка включает:
• пункт назначения;
• номер рейса;
• фамилию и инициалы пассажира;
• желаемую дату вылета.
Программа обеспечивает:
• хранение всех заявок в виде списка;
• добавление и удаление заявок;
• по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением;
• вывод всех заявок.


C++ (Qt)
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
#include <iostream>
#include <locale>
#include <ctime>
#include <string>
using namespace std;
 
struct Aviabileti
 
{
 char punkt_naznachenia[51];
 int nomer_reysa;
 char  fio[51];
 char jelayemaia_data[21];
};
 
int main()
{
int flag=1, i=0, reg, kol=7;
Aviabileti mas[61]; 
 
while (f==1)
 
{
    cout<<"1.Vvod dannix ";
    cout<<"2.Poisk po reysu i date vileta ";
    cout<<"3.Vivod zayavok ";
    cout<<"4.Udaleniye zayavok ";
 
    //добавление данных в массив
    if(reg==1)
{
        for(i=0;i<kol;i++)
        cout<<"Vvedite punkt naznacheniya ";
        cin>>(mas[i].punkt_naznachenia);
        cout<<"Vvedite nomer reysa ";
        cin>>mas[i].nomer_reysa);
        cout<<"Vvedite fio passagira ";
        cin>>(mas[i].fio);
        cout<<"Vvedite datu vileta ";
        cin>>(mas[i].jelayemaia_data);
 
        
        }
 
    if(reg==3)
 
    {
//сортировка значений
int j, min, p1,pp, pp2, temp;
for(i=0;i<kol;i++)
{
min=mas[i].nomer_reysa;
p1=i;
for(j=i;j<kol;j++)
if(mas[j].nomer_reysa<min)
{
min=mas[j].nomer_reysa;
p1=j;
}
temp=mas[i].nomer_reysa;
mas[i].nomer_reysa=mas[p1].nomer_reysa;
mas[p1].nomr_reysa=temp;
strcpy(temp, mas[i].punkt_naznachenia);
strcpy(mas[i].punkt, mas[p1].punkt);
strcpy(mas[p1].punkt_naznachenia,temp);
strcpy(temp, mas[i].tip_samoleta);
strcpy(mas[i].tip_samoleta, mas[p1].tip_samoleta);
strcpy(mas[p1].tip_samoleta, temp);
}
 
for(i=0;i<kol;i++)
        {
        cout<<"Zapis "<<i;
        cout<<"Punkt naznacheniya "<<mas[i].punkt_naznachenia;
        cout<<"Nomer reysa "<<mas[i].nomer_reysa;
        cout<<"Fio passagira "<<mas[i].fio;
        cout<<"Jelaemaya data "<<mas[i].jelayemaia_data;
        }
        }
 
//поиск по рейсу и дате вылета
        if(reg==2)
        {
            cout<<"Vvedite nomer reysa dlya poiska ";
            cin>>pp;
            cout<<"Vvedite datu vileta dlya poiska ";
            cin>>pp2;
            cout<<"Rezultat poiska ";
            fl=0;
        for(int i=0;i<kol;i++)
        {
            if(strcmp(pp2,mas[i].jelayemaia_data, mas[i].nomer_reysa)==0);
            {
        cout<<"Zapis "<<i;
        cout<<"Punkt naznacheniya "<< mas[i].punkt_naznachenia;
        cout<<"Nomer reysa "<<mas[i].nomer_reysa;
        cout<<"Fio passagira "<<mas[i].fio;
        cout<<"Jelayemaia data "<<mas[i].jelayemaia_data;
        
        
            }
        }
 
        if(fl==0)
        cout<<"Biletov s takim punktom naznacheniya net ";
 
        }

двоичное дерево

C++ (Qt)
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
133
134
135
136
137
138
#include <iostream>
#include <conio.h>
#include<time.h>
using namespace std;
 
struct Node
{
    int d;         //Данные элемента
    Node *left;    //Ссылка на левое поддерево
    Node *right;   //Ссылка на правое поддерево
};
Node *first(int d);                    //Формирование первого элемента
Node *search_insert(Node *root, int d); //Поиск с включением
void print_tree(Node *root, int l);     //Обход дерева
 
//-------------------------------------------
void main()
{
    srand(time(0));
    setlocale(0,"Rus");
    int n;             //количество элементов в дереве
    cout << "Введите n: ";
    cin >> n;
    int *b = new int[n];
    cout << "Сгенерированная последовательность: " << endl << endl;
    for(int i = 0; i < n; i ++)
    {
        b[i] = 1 + rand()%100;
        cout << b[i] << " ";
    }
    cout << "\nДерево: " << endl << endl;
    Node *root = first(b[0]);    //Формируем корень дерева
    //Ищем место куда вставить и вставляем новые элементы
    for(int i = 1; i < n; i ++)
    {
        search_insert(root,b[i]);
    }
    print_tree(root,0);            //вывод дерева на экран
    
    int k;               //значения, которые больше заданного к будут удалены
    cout<<"Введите k: "; 
    cin>>k;
    for(int i=0;i<n;i++)
    {
        if(b[i] > k)
        {
            b[i]=-1;
        }
    }
    int o;
    int x=0;
for(int i = 0; i < n; i ++)
    {
        if(b[i]!=-1)
        {
            o=i;
            break;
        }
        else x++;
    }
    if(x==n)
    {
        cout<<"Дерево пустое";
        getch();
        exit(1);
    }
    cout << "\nНовое дерево: " << endl << endl;
    Node *root1 = first(b[o]);
    for(int i = 1; i < n; i ++)
    {
        if(b[i]!=-1)
        {
            search_insert(root1,b[i]);
        }
    }
    print_tree(root1,0);
    delete b;
    getch();
}
 
//--------------------------------------------
//Формирование первого элемента
Node *first(int d)
{
    Node *pv = new Node;      //Создаём элемент
    pv -> d = d;              //Присваиваем значение элементу поля
    pv -> left = 0;           //Ссылка на левое поддерево равна NULL
    pv -> right = 0;          //Ссылка на правое поддерево равна NULL
    return pv;               //Возвращаем адрес элемента
}
 
//---------------------------------------------
 
 
 
//Поиск с включением
Node *search_insert(Node *root,int d)
{
    Node *pv = root, *prev;
    bool found = false;    //Переменная отвечающая за то что нашли ли элемент или нет
    /*Ниже приведён алгоритм поиска, если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/
    while(pv&&!found)
    {
        prev = pv;                       //получаем адрес элемента от которого будем пускать корни
        if(d == pv -> d)found = true;        //совпадение выходим из цикла
        else if(d < pv -> d)pv = pv -> left;   //Всовываемя в левое поддерево
        else pv = pv -> right;             //Всовываемя в правое поддерево 
//Выход из цикла осуществляется, тогда когда нашли свободный адрес : ссылку у дерева : для вставки нового узла */
    }
//---------------------------
/*Если совпало значение элемента со значением элемента который хотим вставить то выходим из функции возвращая адрес элемента
с которым совпало */
    if(found)return pv;               
    //Создание нового узла
    Node *pnew = new Node;
    pnew -> d = d;
    pnew -> left = 0;
    pnew -> right = 0;
    if(d < prev -> d)
    //Присоединение к левому поддереву предка
    prev -> left = pnew;
    else 
    //присоединяем к правому поддереву предка
    prev -> right = pnew;
    return pnew;
}
//---------------------------------------
//Обход дерева
void print_tree(Node *p,int level)
{
    if(p)
    {
        print_tree(p -> left, level + 1);           //Перемещение по левым поддеревьям
        for(int i = 0; i < level; i ++)cout<<"   ";
        cout << p -> d << '\n';                      //вывод значений дерева
        print_tree(p -> right, level + 1);          //Перемещение по правым поддеревьям        
     }
}

нужно как-то соединить эти две программы так, чтобы вместо хранения всех заявок в виде списка было хранение всех заявок в виде двоичного дерева. Но у самой не получается сделать! Помогите, пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2012, 17:32     Из списка в двоичное дерево
Посмотрите здесь:

C++ Двоичное дерево
C++ Двоичное дерево
C++ Двоичное дерево
двоичное дерево C++
Двоичное дерево Хаффмана C++
Двоичное дерево C++

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

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

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