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

Двоичное дерево - C++

Восстановить пароль Регистрация
 
AriStarX
0 / 0 / 0
Регистрация: 19.04.2012
Сообщений: 4
19.04.2012, 18:49     Двоичное дерево #1
Здравствуйте! Помоги задачу решить! Сразу говорю: это не от лени, нам просто мало объясняют! Хотя бы направление дайте, подсказку...Прогу делаю в RAD Studio...
Автоматизированная информационная система на ж/д вокзале содержит сведения об отправлении поездов дальнего следования.
-номер поезда;
-Станция назначения;
-Время отправления.
Данные ИС организованы в виде двоичного дерева
Написать программу, которая:
-Обеспечивает первоначальный ввод данных в ИС и формирование двоичного дерева;
-Производит вывод всего дерева;
-Вводит номер поезда и выводит все данные об этом поезде;
-Вводит название станции назначения и выводит данные о всех поездах, следующих до этой станции.
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

Как организовать двоичное дерево я ещё представляю себе, но осьальное...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sade
2 / 2 / 1
Регистрация: 20.03.2012
Сообщений: 42
20.04.2012, 14:41     Двоичное дерево #2
Могу помочь у меня есть материал всё написано про двоичные деревья ,но реализация на паскале.Помочь?
AriStarX
0 / 0 / 0
Регистрация: 19.04.2012
Сообщений: 4
20.04.2012, 14:43  [ТС]     Двоичное дерево #3
Да, думаю смогу переделать из паскаля в с.
Sade
2 / 2 / 1
Регистрация: 20.03.2012
Сообщений: 42
20.04.2012, 14:48     Двоичное дерево #4
Pascal
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
{$I-,Q-,R-,S-}
const
    FileIn  = 'Input.txt' ;
    FileOut = 'Output.txt';
 
type
    TTreeType = ^TreeType ;
    TreeType  = record
               Left  : TTreeType ;
               Right : TTreeType ;
               Prev  : TTreeType ;
               key   : longint   ;
            end;
 
var
    N     : longint   ;
    Root,Buff : TTreeType ;
 
procedure TreeInsert( var X : TTreeType ; p : longint );
begin
    if X = nil then begin
                 New( X );
                 X^.Prev := Buff ;
                 X^.Left := nil ;
                 X^.Right := nil ;
                 X^.key := p ;
                 Exit ;
                end;
    Buff := X ;
    if p < X^.key then TreeInsert( X^.Left , p )    
              else TreeInsert( X^.Right , p );
end;
 
function TreeSearch( var X : TTreeType ; p : longint ) : TTreeType ;
begin
    TreeSearch := nil ;
    if X <> nil then
      if X^.key = p then TreeSearch := X
            else begin
                  if p < X^.key
                        then TreeSearch := TreeSearch( X^.Left,p )
                    else TreeSearch := TreeSearch( X^.Right,p );
                 end;           
end;
 
function TreeSuccessor( X : TTreeType ) : TTreeType ;
begin
    X := X^.Right ;
    while X^.Left <> nil do
      X := X^.Left ;
    TreeSuccessor := X ;
end;
 
procedure TreeDelete( p : longint );
 
procedure DeleteNode( var z : TTreeType );
var
    y,x : TTreeType ;
begin
    if ( z^.Left = nil ) or ( z^.Right = nil )
        then y := z
        else y := TreeSuccessor( z );
    if y^.Left <> nil then x := y^.Left
              else x := y^.Right ;
        if x <> nil then x^.Prev := y^.Prev ;
    if y^.Prev = nil then Root := x
             else if y = y^.Prev^.Left then y^.Prev^.Left := x
                           else y^.Prev^.Right := x ;
    if y <> z then z^.key := y^.key ;
end;
 
begin
    Buff := TreeSearch( Root , p );
    DeleteNode( Buff );
end;
 
procedure Solution;
var
    i,Chislo : longint ;
    Query    : char    ;
begin
    Assign( Input , FileIn );
    ReSet( Input );
    ReadLn( N );
    for i:=1 to N do
       begin
        Read( Query );
        ReadLn( Chislo );
        Buff := nil ;
        case Query of
          'I' : TreeInsert( Root , Chislo );
          'D' : TreeDelete( Chislo );
          'S' : if TreeSearch( Root , Chislo ) <> nil
                        then WriteLn( 'YES' )
                        else WriteLn( 'NO' );
        end;
       end;
    Close( Input );
end;
 
begin
    Solution;
end.
Добавлено через 59 секунд
тут построение , вставка , удаление , а под свою задачу подгоняй сам!
Yandex
Объявления
20.04.2012, 14:48     Двоичное дерево
Ответ Создать тему
Опции темы

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