Как записать дерево в файл

Обновлено: 03.07.2024

У меня есть некоторый код для создания простого дерева, основанного на указателях на узлы, и я хотел бы записать это дерево (с его данными) в файл, а затем прочитать его обратно из файла в память. Как я могу это сделать ? Вот мой код для создания простого дерева:

2 ответа

у меня есть этот массив char ***three_dim=0; three_dim выделяется и заполняется данными. После этого я должен записать его содержимое в файл и прочитать обратно. Я попытался написать его следующим образом, но это не удалось. FILE *temp; temp=fopen(temp,w);.

Я пытаюсь записать double[] в файл в HDFS, а позже мне нужно будет прочитать его обратно из файла и преобразовать обратно в double[]. Кто-нибудь здесь знает, как это сделать? Спасибо,

Существует два распространенных способа сериализации объектов, имеющих указатели на другие объекты. Первый - заменить указатель смещением в файле, второй-использовать простой индекс. На самом деле способ смещения в основном используется, когда данные используются непосредственно из файла (например, файлы базы данных), в то время как способ индекса больше используется для простого хранения.

Здесь простой способ состоял бы в том, чтобы хранить узлы в файле рекурсивно как left_node - right_node - main_node. Таким образом, когда вы храните узел, вы уже знаете индекс в файле его левого и правого дочерних элементов. Тогда возможна реализация:

Здесь индекс 0 означает указатель null, а индекс не null - это индекс, основанный на единице в файле

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

Вот предложение, я использую препроцессор macro TYPE, чтобы иметь возможность изменять тип и разделенные функции для чтения/записи элемента этого типа, я также использую функцию mk , чтобы легко создавать узел, а не дублировать код, как вы делали для каждого узла.

Для сериализации я использую очень простой способ

'e' указывает на пустой узел
'n' укажите непустой узел, Затем я пишу значение, затем левый, затем правый узел

Я также добавил pr , чтобы легко печатать дерево в качестве функции отладки.

Компиляция и выполнение :

Исполнение под valgrind :

Решение

Это конечно конечно хорошо. Но мне нужно восстановить не сам string, а класс (структуру) с атрибутом(полем) типа string!
У меня получается только выводить только цифровые значения (на char менять не хочу, да и смысл). Но мне нужно восстановить . класс с полем типа string Наверное, нужно восстановить текст этого string'а? Для этого нужно этот текст записать Примеры мне понятны.
А восстановить мне нужно вот это:

И текст там есть. Но его (текста) восстановление не происходит!

Могу бросить функции вывода на каждого элемента на экран.

Об ответах можно только догадываться. Если же data - структура, содержащая string с текстом, то

И мне нужно из Tree восстановить по одному элементу Scope, который находится в указателе T *data.

Добавлено через 5 минут
Как альтернатива (но к сожалению тоже не работает):

через fstream (ifstream and ofstream)

class Scope
string name;
int identificalNum;
float IQ;
. дли н а строки, потом строка, дальше две POD переменных и по кругу Нет, не пойдет.
Мне нужно записать в файл объект класса Scope, а не отдельно по полям класса. Нет, не пойдет.
Мне нужно записать в файл объект класса Scope, а не отдельно по полям класса.

Ты, в этом случае, не сможешь это сделать. std::string использует динамическую память и она не сохранится в файл при простом побайтовом копировании объекта в файл. Плюс к этому, так сохранять "можно" только объекты POD типов, они не имеют нетривиальных конструкторов и не содержат полей с такими конструкторами (также не содержат виртуальных функций, нетривиальных деструкторов, и т.д.). Если объект имеет нетривиальный конструктор, то он должен быть сконструирован с помощью него, другие варианты ведут к UB. И еще плюс к этому, даже если тип - POD, то при таком сохранении всегда нужно помнить про выравнивание.

Прочитай про сериализацию и зачем она нужна. Это в целом решает твою проблему. И объясни хотя бы себе, чем принципиально должна отличаться запись объекта целиком, как ты хочешь, от записи его полей последовательно?

Пытаюсь реализовать алгоритм Хаффмана, который будет сжимать текстовый файл. Уже построено дерево tree, у которого есть:
tree->simvol // char в котором хранится сам символ (например 'a')
tree->code // string, двоичный код для этого символа (например 1001)

Мне нужно написать функцию, которая пройдется по исходному файлу, и будет считывать каждый символ, сверяя его с символами в моем дереве, а найдя нужный - запишет в новый файл последовательность единиц и нулей(tree->code).

Трудность именно в побитовой записи, т.к я не совсем представляю, как ее организовать. Поясню - мне нужно, чтобы ,например, последовательность 10011110 занимала именно 8 бит, т.е единица или ноль занимали бы 1 бит, иначе сжатия не получится(если я просто вместо буквы "а" запишу "1001" как набор символов, а не битов).

Можно создать переменную типа char и переключать в ней отдельные биты с помощью побитового или

В общем очень много где искал и в итоге нашел несколько способов, хотя как по мне все они не особо удобные.
Надеюсь помогу кому-нибудь, а то сам довольно долго разбирался что да как.

Самая простая - создать структуру байта и описать в ней каждый бит.
Причем максимально верно, как я понял, так это сделать это через объединения, хотя я еще не совсем в этом разобрался.

В этом случае записать 1 байт можно например вот так -

Второй способ - преобразовать массив boolean в unsigned char и "побитовым или" писать в нужный бит 1
Если я правильно понял - c = c | (1 << 7); - это запись в 7-й разряд, т.е
00000000
00000010
____________
00000010
и с = 2^7 = 128

а
(c & (1<<7)) != 0) - это проверка на 1 в 7-м разряде
т.е
00000111
00000010
___________
00000010
результат !=0, значит есть единица в 7-м разряде.

Мне же удобно было держать коды в string , поэтому я переделал под нее -

Еще есть вариант, но я до него не дошел - это писать все непосредственно в буфер, а потом записывать весь буфер целиком, а не по байтам, как я.

В общем как-то так, поправьте меня, если где ошибся или можно улучшить/сократить функцию..

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

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

Рис. 1 Бинарное дерево

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

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

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

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

Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение ~~банкета~~ статьи.

Читайте также:

Как записать дерево в файл

2 ответа

Похожие вопросы:

Решение