Сохранение дерева в файле

Сохранить бинарное дерево в файл

Подскажите, пожалуйста, как сохранить бинарное дерево в файл?
Суть задачи: необходимо создать бинарное дерего, добавить к нему листы, просмотреть его, а так же напечатать все элементы каждого листа. Все это должно сохраняться и считываться из файла. При попытке сохранить выдает exit code 103.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

type zap=record nomer:string[5]; st_otp:string[15]; st_pr:string[15]; vr_otp:string[5]; vr_pr:string[5]; stoim:string[10]; end; TreePtr=^Tree; Tree=record Data:zap; Left,Right:TreePtr; end; var top:TreePtr; Z:zap; i: integer; number: integer; f: file of zap;

procedure sohr(top:treeptr); begin rewrite(f); while top<>nil do begin write(f,top^.data); end; readln; close(f); end;

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

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно.

бинарное дерево?Файл?
объясните пожалуйста что означает слово бинарное?

файл, структура, бинарное дерево
——————————————————————————— Доброго времени.

write(f,top^.data.nomer); write(f,top^.data.st_otp); write(f,top^.data.st_pr); write(f,top^.data.vr_otp); write(f,top^.data.vr_pr); write(f,top^.data.stoim);

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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207

program lab10; uses crt; type zap=record nomer:string[5]; st_otp:string[15]; st_pr:string[15]; vr_otp:string[5]; vr_pr:string[5]; stoim:string[10]; end; TreePtr=^Tree; Tree=record Data:zap; Left,Right:TreePtr; end; var top:TreePtr; Z:zap; i: integer; number: integer; f: file of zap;  function AddTree (top: treeptr; newnode: zap):treeptr; ; newnode – добавление значения в дерево} begin if top=nil then begin new(top); top^.data:=newnode; top^.left:=nil; top^.right:=nil; end else if top^.data.nomer>newnode.nomer then top^.left:=addtree(top^.left,newnode) else top^.right:=addtree(top^.right,newnode); addtree:=top end; procedure readfile(top: treeptr); var p:treeptr; r:zap; begin top:=nil; reset(f); while not eof(f) do begin read(f,r); top:=addtree(top,r); end; close(f); end; procedure sohr(top:treeptr); begin rewrite(f); if top<>nil then begin sohr(top^.left); sohr(top^.right); write(f,top^.data); end; close(f); end; procedure orgtree; begin reset(f); seek(f,filesize(f)); writeln('Организация дерева'); writeln(' '); writeln('____________________________________________________________________'); writeln('| | Станция | Время | Стоимость |'); writeln('|№ поезда |_________________________| __________________| билета |'); writeln('| | отправление | прибытие |отправление|прибытие| (грн) |'); writeln('|___________________________________________________________________|'); top:=nil; while true do begin writeln('Для завершения нажмите *'); readln(z.nomer); if z.nomer='*' then exit; readln(z.st_otp); readln(z.st_pr); readln(z.vr_otp); readln(z.vr_pr); readln(z.stoim); write(f,z); top:=addtree(top,z); end; sohr(top); end; procedure dobl; begin reset(f); seek(f,filesize(f)); writeln(''); writeln('Добавления листа к дереву'); writeln('____________________________________________________________________'); writeln('| | Станция | Время | Стоимость |'); writeln('|№ поезда |_________________________| __________________| билета |'); writeln('| | отправление | прибытие |отправление|прибытие| (грн) |'); writeln('|___________________________________________________________________|'); readln(z.nomer); readln(z.st_otp); readln(z.st_pr); readln(z.vr_otp); readln(z.vr_pr); readln(z.stoim); write(f,z); top:=addtree(top,z); sohr(top); end; procedure prosmotr(top:treeptr); begin reset(f); seek(f,0); writeln(''); writeln('Просмотр дерева'); writeln('____________________________________________________________________'); writeln('| | Станция | Время | Стоимость |'); writeln('|№ поезда |_________________________| __________________| билета |'); writeln('| | отправление | прибытие |отправление|прибытие| (грн) |'); writeln('|___________________________________________________________________|'); if top<>nil then begin read(f,z); prosmotr(top^.left); writeln(i,' ',top^.data.nomer,' ',top^.data.st_otp,' ',top^.data.st_pr, ' ',top^.data.vr_otp,' ',top^.data.vr_pr,' ',top^.data.stoim); i:=i+1; prosmotr(top^.right); end; close(f); end; procedure otobr(top:treeptr; otstup:integer); begin reset(f); seek(f,0); if top<>nil then begin read(f,z); otstup:=otstup+3; otobr(top^.left,otstup); writeln('':otstup,top^.data.nomer); otobr(top^.right,otstup); end; close(f); readln; end; procedure printlist (anode:treeptr); begin reset(f); seek(f,0); writeln(''); writeln('Просмотр всех элементов листьев дерева'); writeln('____________________________________________________________________'); writeln('| | Станция | Время | Стоимость |'); writeln('|№ поезда |_________________________| __________________| билета |'); writeln('| | отправление | прибытие |отправление|прибытие| (грн) |'); writeln('|___________________________________________________________________|'); if anode<>nil then begin read(f,z); if(anode^.left=nil) and (top^.right=nil) then printlist(anode^.left); writeln(' ',anode^.data.nomer,' ',anode^.data.st_otp,' ',anode^.data.st_pr, ' ',anode^.data.vr_otp,' ',anode^.data.vr_pr,' ',anode^.data.stoim); printlist(anode^.right); end; close(f); readln; end; begin assign(f,'data.txt');  reset(f);  if IOResult=0 then writeln('Запись в существующий файл') else begin rewrite(f);  writeln('Запись в новый файл'); end; readln; repeat; clrscr; writeln(' _______________________________________); writeln('| 1 – Организация двоичного дерева |'); writeln('| 2 – Добавления листа к дереву |'); writeln('| 3 – Просмотр дерева |'); writeln('| 4 – Просмотр всех элементов листьев дерева |'); writeln('| 5 - Выход |'); writeln('|________________________________________|'); writeln(' Выбор пункта меню '); readln(number); case number of 1:orgtree; 2:dobl; 3:begin i:=1; prosmotr(top); otobr(top,1); writeln('Нажмите клавишу Enter'); readln; end; 4:begin printlist(top); readln; end; end; until number=5; end.

Источник

Как в файле хранить дерево?

есть дерево каждому узлу которого поставлено в соответсвие некоторое число.

порядок количества узлов ожидается более милиарда.

меня интересует способ хранения этого зверька в файле оптимизированный на максимально быстрый доступ к значению узла.

Re: Как в файле хранить дерево?

Если дерево бинарное — то можно в виде кучи. Максимальное время доступа — logN по основанию 2, где N — количество элементов.

Re: Как в файле хранить дерево?

Если операций доступа много и они частые то все равно придется все дерево в память грузануть, так что в принципе все равно как оно в файле будет, а если операций немного и нечастые то тогда тоже нет смысла огород городить 🙂

Re: Как в файле хранить дерево?

>Если операций доступа много и они частые то все равно придется все дерево в память грузануть, так что в принципе все равно как оно в файле будет,

все нереально. миллиард интов это четыре гига озу только на значчения а надо еще и обвязку:(

Re: Как в файле хранить дерево?

Re: Как в файле хранить дерево?

Как хорошо, что СУБД разрабатывают не такие, как ты.

Re: Как в файле хранить дерево?

Представь себе, без разницы. Не-бинарное на бинарное отображается элементарно.

Re: Как в файле хранить дерево?

Дерево для поиска используется или для других целей? Нужно ли сохранять структуру этого дерева один-в-один? Нужна ли быстрая загрузка _всего_ дерева в память или быстрое выполнение определенных операций? Конкретнее задачу поставь.

Re: Как в файле хранить дерево?

Насчет третьего вопроса после повторного прочтения все прояснилось. Остальные вопросы в силе.

Re: Как в файле хранить дерево?

Re: Как в файле хранить дерево?

tailgunner, это подойдет только если дерево нужно именно для поиска и структуру исходного дерева (если таковое вообще есть в исходной задаче, чего по постановке не понятно) сохранять не нужно.

Re: Как в файле хранить дерево?

Без точной формулировки это лучший совет, на который я способен 🙂 Если нужно сохранять структуру исходного дерева, то ХЗ. нужна полная формулировка задачи. Может, там нужна хеш-функция и mmap-окно.

Re: Как в файле хранить дерево?

>Дерево для поиска используется или для других целей?

1. для поиска
2. добавление новых узлов и ветвей между поисками тож должно быть быстрым

>Нужно ли сохранять структуру этого дерева один-в-один?

сохранять порядок веток не нужно

>Нужна ли быстрая загрузка _всего_ дерева в память или быстрое выполнение определенных операций? Конкретнее задачу поставь.

Re: Как в файле хранить дерево?

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

Re: Как в файле хранить дерево?

Спасибо но мое дерево типа B а не B+.

причем с возможным количеством веток из одного узла порядка миллиона.

возможно мне действительно нужно отображать на какое нить другое дерево типа бинарного для работы и хранениея.

пока ничего умнее в голову не лезет

Re: Как в файле хранить дерево?

Так и используй Б-дерево. Оно идеально ложится на твою задачу, в отличие от бинарного. При работе с диском узким местом является количество операций чтения и именно структуры типа Б-дерева оптимизируют поиск по этому критерию. Бинарное дерево будет слишком дорогостоящим.

Re: Как в файле хранить дерево?

> Спасибо но мое дерево типа B а не B+.

> причем с возможным количеством веток из одного узла порядка миллиона

B-деревья с этим справляются. Кроме того, ты можешь просто вести подсчет количества ключей (упрощенно, хранить в дереве не struct < int key; >а struct < int key; int nkeys; >).

Re: Как в файле хранить дерево?

вобщем всем спасибо — натолкнули на светлые мысли

Источник