Как сохранить дерево в файл, а после его загрузить?
Если дерево нормально сбалансировано: пишем корень, прямо как есть. далее обходим дерево и пишем все проходимые узлы в направлении движения вниз. всегда придерживаемся одного правила движения, например сначала идем налево, по возвращении — направо. все указатели в файле особого смысла не имеют. Но по потому, что они не NULL при чтении можно будет понять, что в данной точке мы более не углублялись. А зная это мы можем прочитать блоки в точно таком порядке как писали. При чтении меняем все указатели на новые
25 ноя 2018 в 16:20
@Mike: А как это связано с тем, сбалансировано дерево или нет?
Как записать/прочитать дерево из файла?
Пишу алгоритм сжатия текстового документа методами Хаффмана и Шеннона-Фано.
Уже почти все готово — т.е создается дерево, по нему создаются коды для каждого символа и с их помощью кодируется текст.
Осталось только как-то записать и прочитать дерево, по которому можно будет расшифровать сообщение..
Вот структура для Шеннона-Фано:
struct spisok//список < char ch;//символ string code;//код double k;//вероятность spisok *next; >*myspisok=NULL; struct tree //дерево < tree *left,*right; spisok *s;//содержит в себе список >*mytree=NULL;Поясню — у каждого элемента дерева есть список, у листа этот список состоит всего из одного элемента, он то и нужен.
По сути можно вообще удалить все списки кроме списка у дерева.
Структура для Хаффмана вроде попроще —
struct spisok < //список деревьев FailFish char simvol; string code; int kol; spisok *next; spisok *prev; spisok *left; spisok *right; >*head,*sortlist,*tree;Тут *next и *prev не нужны, нужно записать, как я думаю, только simvol,*left,*right
Как это можно провернуть?
Функция расшифровки по дереву у меня такая —
for(int i=0;i if (t->left == NULL && t->right == NULL)//дошли до листа < fwrite(&(t->s->ch),sizeof(char),1,decrypted);//записываем символ из листа couts->ch;//выводим его t=head;//поднимаемся назад к голове k++; > if (final_code[i]=='1') t=t->right;//если 1 - идем вправо else t=t->left;//иначе - влево > - Вопрос задан более трёх лет назад
- 3524 просмотра
Как сохранить бинарное дерево в файл c
Здравствуйте! Не знаю где искать помощи, решил обратиться сюда, надеюсь поможете =)
Мне препод в универе дал задание, звучит оно примерно так: «Имеется текстовый файл с текстом из книги Война и Мир. Нужно построить бинарное дерево из слов входящих в этот файл. Добавление элемента в дерево зависит от количества вхождений данного слова в файл.»
Надеюсь суть понятна.
Я почти сделал эту программу. Сначала сделал бинарное дерево чтобы подсчитать кол-во вхождений каждого слова и отсортировать его с помощью strcmp. Но потом, когда делаю второе дерево из элементов первого дерева то у меня возникает переполнение стека. Сделал ограничение до 5000 и все работает, но там в дереве еще остаются более 20000 слов. Бинарное дерево я строю рекурсивными функциями.
Расскажу саму программу.
Bunch — класс одного элемента дерева. Он содержит ссылки на левый и правый элемент такого же класса (дети элемента).
Bunch.value — кол-во вхождений слова в текст
Bunch.name[40] — само слово
class Bunch public:
int value;
char name[30];
Bunch* left_child;
Bunch* right_child;
Bunch :: Bunch() left_child = 0;
right_child = 0;
value = 0;
>;
Собственно это всё, что я вынес в отдельные файлы. Теперь расскажу про исходник с функцией main()
Я создам новое сообщение ниже с кодом этой функцией, не получается сюда
| LordAlex91 |
| Посмотреть профиль |
| Найти ещё сообщения от LordAlex91 |
Регистрация: 18.02.2012
Сообщений: 4
Вот сам код этой функции. Почему то отступы удалились =(
using AreaBunch :: Bunch;
void MakeTree(Bunch* root, char* inName)
if ((root) && (root -> value) == 0) for (int i = 0; i < strlen(inName); i++)
root -> name[i] = inName[i];
root -> name[strlen(inName)] = ‘\0’;
root -> value = 1;
> else
if (strcmp(root -> name, inName) == 0) < //совпадение
root -> value = root -> value + 1;
>
else
if (strcmp(root -> name, inName) == 1) //name > inName
if (!root -> left_child)
root -> left_child = new Bunch;
MakeTree(root -> left_child, inName);
>
else
if (strcmp(root -> name, inName) == -1) //name < inName
if (!root -> right_child)
root -> right_child = new Bunch;
MakeTree(root -> right_child, inName);
>;
>;
void MakeTree2(int& value, char* name, Bunch* new_root) if ((new_root) && (new_root -> value == 0))
new_root -> value = value;
for (int i = 0; i < strlen(name); i++)
new_root -> name[i] = name[i];
new_root -> name[strlen(name)] = ‘\0’;
>
else
if (value < new_root ->value)
if (!new_root -> left_child)
new_root -> left_child = new Bunch;
MakeTree2(value, name, new_root -> left_child);
> else
if (value >= new_root -> value) if (!new_root -> right_child)
new_root -> right_child = new Bunch;
MakeTree2(value, name, new_root -> right_child);
>;
>;
void CreateTree2(Bunch* new_root) int read_value;
char read_name[30];
FILE* new_output = fopen(«output2.txt», «w+»);
FILE* input = fopen(«output.txt», «r»);
int counter = 0;
while (!feof(input))
if (counter > 5000) break;
fscanf(input,»%s %d», &read_name, &read_value);
std :: cout MakeTree2(read_value, read_name, new_root);
>;
void PrintTree(Bunch* root, FILE* f_pointer) if (root) PrintTree(root -> left_child,f_pointer);
fprintf(f_pointer, «%s %d\n», root -> name, root -> value);
PrintTree(root -> right_child,f_pointer);
>;
int main()
Bunch* root = new Bunch;
root -> value = 5;
root -> name[0] = ‘в’;
root -> name[1] = ‘ы’;
root -> name[2] = ‘\0’;
//Создали корень дерева
FILE* output = fopen(«output.txt»,»w+»);
FILE* file_p = fopen(«Book_rus.txt»,»r»);
if ((file_p == NULL) || (output == NULL))
std :: cout getch();
return 1;
>;
if (strlen(fgword) > 1)
MakeTree(root, fgword);
>;
Bunch* root2 = new Bunch;
CreateTree2(root2);
FILE* output2 = fopen(«output2.txt», «w+»);
PrintTree(root2, output2);
Как сохранить бинарное дерево в файл c
Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
30.11.05 19:56: Перенесено из ‘C/C++. Прикладные вопросы’
Re: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 25.11.05 15:11 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
1) xml или любой другой деревянный язык
2) обход дерева в глубину (parent-left-right) :
Рекурсивная запись и рекурсивное же чтение. Поскольку некоторые дочерние узлы могут отсутствовать, то нужно записывать признаки их наличия (2-битовое поле на один родительский узел или по булеву признаку каждому индивидуально).
3) обход дерева из глубины (left-right-parent) :
Фактически, в файле оказывается программа для стекового автомата: взять два указателя на узлы (возможно, нулевые) со стека, прочитать данные из файла, сконструировать родительский узел и запихать в стек.
3) поперечный обход дерева (left-parent-right) : надо подумать.
Плюс состоит в том, что даже на несбалансированном дереве будут затраты O(1) на глубину стека как при записи, так и при чтении. Минус — в нетривиальности.
Перекуём баги на фичи!
Re[2]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 25.11.05 16:01 |
| Оценка: |
1) Это нужно написать на С++.
2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?
3) Дерево не сбалансированно.
А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?
Re: Сохранение и востановление дерева в файл.
| От: | diro |
| Дата: | 25.11.05 16:16 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
Вопрос как дерево хранится . Например можно хранить его в массиве, где left, right указывают на индекы в этом массиве ( -1 читай, никуда не указывают ). Нулевой элемент — это всегда node. Т.е. тогда возьмешь и массив в файл сдампиш — и дело с концом. Ну там еще размер куда — нить сунуть придется. Возможно, что это можно использовать как некий переходник.
struct TreeItem
TreeData data;
int left, right;
>;
Re[2]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 25.11.05 17:23 |
| Оценка: |
Здравствуйте, diro,
Вот дерево
template class T> class CTree_Item < private: struct TItem < T Data; int left; int right; >Item; CTree_Item *left_child; CTree_Item *right_child; CTree_Item *parent; CTree_Item(T const &d, int l,int r, CTree_Item *lchild, CTree_Item *rchild, CTree_Item *p); CTree_Item(CTree_Item *copy); public: T const& Get_Data(); int const& Get_Left(); int const& Get_Right(); void Set_Data(T &d); void Set_Left(int const &x); void Set_Right(int const &x); . friend CTree; >; template class T> class CTree < private: CTree_Item *Root; void Redefintion(CTree_Item *p, int x, bool bl); public: CTree(); ~CTree(); void Add_Item(int lt, T d); T Delete_Item(int lt, int rt); void Save_to_file(char file[255]); void Load_from_file(char file[255]); . >Для оформления С++ного кода пользуйся тэгом [c]-[/c]. Кодт
Re[3]: Сохранение и востановление дерева в файл.
| От: | Кодт | |
| Дата: | 25.11.05 23:56 | |
| Оценка: | +1 | |
Здравствуйте, AndreyGor, Вы писали:
AG>Здравствуйте, Кодт,
AG>1) Это нужно написать на С++.
Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.
AG>2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?
Если узла нет, то пишешь маркер «здесь узла нет». А если есть, то «здесь узел есть, читай дальше». Например.
Можно и другими способами — скажем, для поперечного обхода можно просто указывать глубину каждого узла — по ней (и по порядку следования) дерево восстанавливается однозначно.
AG>3) Дерево не сбалансированно.
Не имеет значения.
AG>А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?
Открой файл заранее и передай его хэндл или ссылку на его объект внутрь рекурсивной функции.
struct TreeNode < Some data; shared_ptrleft, right; >; // рекурсивные функции - operator> для чтения - принимают ссылки на потоки ostream& operator << (ostream& ost, shared_ptrnode) < if(!node) ost '-'; // маркер "здесь узла нет" else ost '+' // маркер "здесь узел есть" data left // мы твёрдо знаем, что сперва запишем (возможно, отсутствующий) левый узел right; // а затем - правый. return ost; > istream& operator >> (istream& ist, shared_ptr &node) < char exist; ist >> exist; // сперва прочтём маркер if(!exist) node = shared_ptr(); // нулевой указатель else < node = shared_ptr(new TreeNode); ist >> node->data >> node->left // читаем левый узел (возможно, что он будет нулевым. ) >> node->right; // читаем правый узел. > return ist; > // "лицевые" функции создают потоки внутри и вызывают рекурсивные функции, передавая туда ссылки void save_tree(string filename, shared_ptr root) < ostream ost(filename); ost void load_tree(string filename, shared_ptr& root) < istream ist(filename); ist >> root; >Перекуём баги на фичи!
Re[4]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 26.11.05 16:53 |
| Оценка: |
Здравствуйте, Кодт, Вы писали:
К>Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.
Нужно примерно следующее:
реализовать родовой класс бинарного дерева с указателями на производные узлы.
Класс должен поддерживать типовые для работы с деревьями функции.
Под типовыми для работы с деревьями понимаются следующие функции:
1. Создание пустого дерева
2. Включение нового узла в структуру дерева
3. Удаление узла из структуры дерева
— с уничтожением производных узлов
— без уничтожения производных узлов
4. Обход дерева и распечатка структуры дерева
5. Поиск узла с заданным значением в информационном поле
6. Запись дерева в файл
7. Чтение дерева из файла
8. Уничтожение дерева
Реализовать нужно на VS в виде консольного приложения.
В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!
Re[5]: Сохранение и востановление дерева в файл.
| От: | Кодт | |
| Дата: | 26.11.05 19:34 | |
| Оценка: | 4 (1) | |
Здравствуйте, AndreyGor, Вы писали:
AG>Нужно примерно следующее:
AG>реализовать родовой класс бинарного дерева с указателями на производные узлы.
Просто чтобы договориться о терминах.
Что такое родовой класс? Generic, что ли?
Производные узлы — имеется в виду, что элементы дерева могут быть производных классов, или это просто дочерние узлы?
AG>Класс должен поддерживать типовые для работы с деревьями функции.
AG>Под типовыми для работы с деревьями понимаются следующие функции:
AG>1. Создание пустого дерева
AG>2. Включение нового узла в структуру дерева
AG>3. Удаление узла из структуры дерева
AG> — с уничтожением производных узлов
AG> — без уничтожения производных узлов
AG>4. Обход дерева и распечатка структуры дерева
Есть несколько разных обходов:
— нисходящий (родитель-дети)
— восходящий (дети-родитель); например, так вычисляются формулы
— поперечный (левый-родитель-правый); если дерево упорядочено, то такой обход сохраняет порядок элементов
— в ширину (корень, дети, внуки, правнуки. )
и т.п.
Интересно, что для первых трёх видов обхода не нужна ни рекурсия, ни дополнительные коллекции. Достаточно, чтобы дочерний узел ссылался на родителя.
AG>5. Поиск узла с заданным значением в информационном поле
Если дерево не упорядочено, то поиск сводится к обходу.
AG>6. Запись дерева в файл
AG>7. Чтение дерева из файла
AG>8. Уничтожение дерева
AG>Реализовать нужно на VS в виде консольного приложения.
AG>В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!
Пример рекурсивной функции, сохраняющей дерево в нисходящем обходе, я уже привёл. Можешь доработать его напильником (ну или кувалдой), и будет щасте.
Если дерево несбалансировано, то глубина рекурсии может оказаться непозволительно большой. Поэтому стоит задуматься о том, чтобы написать нерекурсивную версию функций записи, а главное, чтения.
Интересный этюд для программирования
Перекуём баги на фичи!
Re[6]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 27.11.05 08:34 |
| Оценка: |
Здравствуйте, Кодт, Вы писали:
К>Просто чтобы договориться о терминах.
К>Что такое родовой класс? Generic, что ли?
К>Производные узлы — имеется в виду, что элементы дерева могут быть производных классов, или это просто дочерние узлы?
Родовой класс — это шаблон.
Производные узлы — это просто дочерние узлы.
По поводу обхода дерева: это все понятно, спасибо. Не понимаю как после записи в файл восстановить его структуру в точности такой какой она была.
Re[7]: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 28.11.05 13:06 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>По поводу обхода дерева: это все понятно, спасибо. Не понимаю как после записи в файл восстановить его структуру в точности такой какой она была.
А вот и подумай, как
Будем считать, что отсутствующий дочерний узел (нуль) — это фиктивный лист.
Выполняем обход PLR. Почему именно его: в нём родительские узлы появляются до своих дочерних, так что при чтении будем сразу наращивать финальное дерево, а не держать ничего в уме.
При записи: встречаем нормальный узел, пишем маркер «есть» и данные узла; встречаем фиктивный — пишем «нет».
При чтении: держим в уме предыдущий посещённый узел. Читаем маркер (и данные, если «есть»), создаём новый узел (либо нуль, если «нет») и прикрепляем его к дереву туда, где он должен был появиться при обходе. Переходим на него (или перескакиваем, если он фиктивный — как обычно).
Единственная тонкость — как отличать свеже-подцепленный фиктивный узел от ещё не подцепленного. (При обходе).
Можем выполнить обход LRP. В этом случае дерево будет строиться из поддеревьев, и потребуется стек полуфабрикатов (в худшем случае — линейной глубины). С помощью одного хитрого хода (правда, ценой гораздо бОльшего времени работы при записи) можно сократить его до логарифмической глубины. А именно, нужно писать сперва более глубокие поддеревья. И указывать, в каком порядке следовали дочерние узлы свежесоздаваемого родителя — L,R или R,L.
Я ещё не знаю решения (но знаю подходы), и расцениваю эту задачу как этюд. Попробуй решить её сам.
Перекуём баги на фичи!
Re: Сохранение и востановление дерева в файл.
| От: | eao197 | http://eao197.blogspot.com |
| Дата: | 28.11.05 13:13 | |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
SObjectizer: Агентно-ориентированное программирование на C++.
Re[2]: Сохранение и востановление дерева в файл.
| От: | eao197 | http://eao197.blogspot.com |
| Дата: | 28.11.05 13:19 | |
| Оценка: | 23 (1) | |
Здравствуйте, eao197, Вы писали:
AG>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
E>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
SObjectizer: Агентно-ориентированное программирование на C++.
Re[3]: Сохранение и востановление дерева в файл.
| От: | AndreyGor |
| Дата: | 28.11.05 14:46 |
| Оценка: |
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, eao197, Вы писали:
AG>>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.
E>>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.
E>Например, вот здесь: http://it.kgsu.ru/C_DIN/din_0065.html
Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей. А я не уверен, что у меня будет именно так!
Re[4]: Сохранение и востановление дерева в файл.
| От: | Кодт |
| Дата: | 30.11.05 14:06 |
| Оценка: |
Здравствуйте, AndreyGor, Вы писали:
AG> Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей. А я не уверен, что у меня будет именно так!
А ты используй фиктивные листья!