Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

Здравствуйте, AndreyGor, Вы писали:

AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

1) xml или любой другой деревянный язык

2) обход дерева в глубину (parent-left-right) :
Рекурсивная запись и рекурсивное же чтение. Поскольку некоторые дочерние узлы могут отсутствовать, то нужно записывать признаки их наличия (2-битовое поле на один родительский узел или по булеву признаку каждому индивидуально).

3) обход дерева из глубины (left-right-parent) :
Фактически, в файле оказывается программа для стекового автомата: взять два указателя на узлы (возможно, нулевые) со стека, прочитать данные из файла, сконструировать родительский узел и запихать в стек.

3) поперечный обход дерева (left-parent-right) : надо подумать.
Плюс состоит в том, что даже на несбалансированном дереве будут затраты O(1) на глубину стека как при записи, так и при чтении. Минус — в нетривиальности.

Здравствуйте, Кодт,

1) Это нужно написать на С++.
2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?
3) Дерево не сбалансированно.
А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?

Здравствуйте, AndreyGor, Вы писали:

AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

Вопрос как дерево хранится . Например можно хранить его в массиве, где left, right указывают на индекы в этом массиве ( -1 читай, никуда не указывают ). Нулевой элемент — это всегда node. Т.е. тогда возьмешь и массив в файл сдампиш — и дело с концом. Ну там еще размер куда — нить сунуть придется. Возможно, что это можно использовать как некий переходник.

struct TreeData
{
};

struct TreeItem
{
TreeData data;
int left, right;
};

TreeItem* MyTree;

Здравствуйте, 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<T>;
};
template <class T>
class CTree
{
private:
    CTree_Item<T> *Root;   
    void Redefintion(CTree_Item<T> *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]);
       ........
}

Здравствуйте, AndreyGor, Вы писали:

AG>Здравствуйте, Кодт,

AG>1) Это нужно написать на С++.

Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.

AG>2) Вопрос в том, как потом восстановить инфу в том же порядке, что и был! Каких-то узлов ведь может и не быть! Да и какой из них правый, а какой левый?

Если узла нет, то пишешь маркер "здесь узла нет". А если есть, то "здесь узел есть, читай дальше". Например.
Можно и другими способами — скажем, для поперечного обхода можно просто указывать глубину каждого узла — по ней (и по порядку следования) дерево восстанавливается однозначно.

AG>3) Дерево не сбалансированно.

Не имеет значения.

AG>А еще возник вопрос по С++: как написать рекурсивную функцию, чтобы не открывать файл каждый раз?

Открой файл заранее и передай его хэндл или ссылку на его объект внутрь рекурсивной функции.

Пример

struct TreeNode
{
  Some data;
  shared_ptr<TreeNode> left, right;
};

// рекурсивные функции - operator<< для записи и operator>> для чтения - принимают ссылки на потоки
ostream& operator << (ostream& ost, shared_ptr<TreeNode> node)
{
  if(!node)
    ost << '-'; // маркер "здесь узла нет"
  else
    ost << '+' // маркер "здесь узел есть"
        << node->data
        << node->left // мы твёрдо знаем, что сперва запишем (возможно, отсутствующий) левый узел
        << node->right; // а затем - правый...
  return ost;
}
istream& operator >> (istream& ist, shared_ptr<TreeNode> &node)
{
  char exist; ist >> exist; // сперва прочтём маркер
  if(!exist)
    node = shared_ptr<TreeNode>(); // нулевой указатель
  else
  {
    node = shared_ptr<TreeNode>(new TreeNode);
    ist >> node->data
        >> node->left // читаем левый узел (возможно, что он будет нулевым...)
        >> node->right; // читаем правый узел...
  }
  return ist;
}

// "лицевые" функции создают потоки внутри и вызывают рекурсивные функции, передавая туда ссылки
void save_tree(string filename, shared_ptr<TreeNode> root)
{
  ostream ost(filename);
  ost << root;
}
void load_tree(string filename, shared_ptr<TreeNode>& root)
{
  istream ist(filename);
  ist >> root;
}

Здравствуйте, Кодт, Вы писали:

К>Что тебе нужно? Примеры, готовые решения? Тогда уточни, какими средствами (библиотеками) ты располагаешь — во-первых, и более подробно опиши цель — во-вторых.

Нужно примерно следующее:
реализовать родовой класс бинарного дерева с указателями на производные узлы.
Класс должен поддерживать типовые для работы с деревьями функции.

Под типовыми для работы с деревьями понимаются следующие функции:
1. Создание пустого дерева
2. Включение нового узла в структуру дерева
3. Удаление узла из структуры дерева
— с уничтожением производных узлов
— без уничтожения производных узлов
4. Обход дерева и распечатка структуры дерева
5. Поиск узла с заданным значением в информационном поле
6. Запись дерева в файл
7. Чтение дерева из файла
8. Уничтожение дерева

Реализовать нужно на VS в виде консольного приложения.

В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!

Здравствуйте, 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>В реализации просто дерева проблем нет. А вот при работе с файлами чегой-то не получаеться!

Пример рекурсивной функции, сохраняющей дерево в нисходящем обходе, я уже привёл. Можешь доработать его напильником (ну или кувалдой), и будет щасте.

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

Здравствуйте, Кодт, Вы писали:

К>Просто чтобы договориться о терминах.
К>Что такое родовой класс? Generic, что ли?
К>Производные узлы — имеется в виду, что элементы дерева могут быть производных классов, или это просто дочерние узлы?
Родовой класс — это шаблон.
Производные узлы — это просто дочерние узлы.

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

Здравствуйте, AndreyGor, Вы писали:

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

А вот и подумай, как

Будем считать, что отсутствующий дочерний узел (нуль) — это фиктивный лист.

Выполняем обход PLR. Почему именно его: в нём родительские узлы появляются до своих дочерних, так что при чтении будем сразу наращивать финальное дерево, а не держать ничего в уме.
При записи: встречаем нормальный узел, пишем маркер "есть" и данные узла; встречаем фиктивный — пишем "нет".
При чтении: держим в уме предыдущий посещённый узел. Читаем маркер (и данные, если "есть"), создаём новый узел (либо нуль, если "нет") и прикрепляем его к дереву туда, где он должен был появиться при обходе. Переходим на него (или перескакиваем, если он фиктивный — как обычно).
Единственная тонкость — как отличать свеже-подцепленный фиктивный узел от ещё не подцепленного. (При обходе).

Можем выполнить обход LRP. В этом случае дерево будет строиться из поддеревьев, и потребуется стек полуфабрикатов (в худшем случае — линейной глубины). С помощью одного хитрого хода (правда, ценой гораздо бОльшего времени работы при записи) можно сократить его до логарифмической глубины. А именно, нужно писать сперва более глубокие поддеревья. И указывать, в каком порядке следовали дочерние узлы свежесоздаваемого родителя — L,R или R,L...

Я ещё не знаю решения (но знаю подходы), и расцениваю эту задачу как этюд. Попробуй решить её сам.

Здравствуйте, AndreyGor, Вы писали:

AG>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.

Здравствуйте, eao197, Вы писали:

AG>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

E>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.

Например, вот здесь: http://it.kgsu.ru/C_DIN/din_0065.html

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, eao197, Вы писали:

AG>>>Уважаемые, подскажите какой-нинь способ сохранения бинарного неупорядоченного дерева в файл и восстановления его структуры в памяти!! А то что-то ничего не получается.

E>>По-моему, есть такая штука, как код Прюфера, которая как раз является способом записи и восстановления произвольных деревьев. Поищи описание, там, как мне помнится, не так уж все и сложно было.

E>Например, вот здесь: http://it.kgsu.ru/C_DIN/din_0065.html

Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей!!!!!! А я не уверен, что у меня будет именно так!

Здравствуйте, AndreyGor, Вы писали:

AG> Код Пpюфеpа взаимно однозначно кодиpует деpевья лишь в том случае, когда каждая веpшина либо является листом, либо имеет двух сыновей!!!!!! А я не уверен, что у меня будет именно так!

А ты используй фиктивные листья!