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

Question

[Алексей Майрин]

Привет всем!
Может есть что-то по именно рекурсивной записи из файла в бинарное дерево?
Буду благодарен!)

Comments

[Mercury13]

Задача-то какая? Хранить деревяху в файле?

[Mercury13]

Ещё одна возможная задача: дерево — всего лишь индекс, а реально наши данные представляют собой линейный список.

[Алексей Майрин]

Mercury13: Задача: хранить данные в файле, которые нужно записать в бинарное дерево, почему именно рекурсивное просил , т.к рекурсией , проще обход реализовать, как я понял
Вообще делаю акинатор, по этому такое надо

Answer 1

[Mercury13]

Акинатор — задача сложная: там и «большие данные», и вопросы, уточняющие информацию о герое и позволяющие вписать его в стандартную матрицу, и прочее. Но это офтоп, о дереве.

Таким образом, задача — хранить дерево в файле с возможностью считать его в том же виде, как и записано.

В боевой программе я бы посоветовал использовать XML или его двоичный аналог.

<node question="У него есть колёса?">
  <yes><answer value="наркоман" /></yes>
  <no><node question="Он живёт в лесу?">…</node></no>
</node>

От двоичного аналога требуется работать с блоками (микропотоками внутри большого файла) и с директориями.

Если считать, что наша XML-библиотека работает методом дописывания тэгов в конец файла, будет такой код записи (считаем, что код объектно-ориентированный, с классами Развилка и Ответ, поддерживающими интерфейс Узел).

функ записатьФайл(xml : XmlПисатель)
  xml.записатьЗаголовок
  xml.открытьТэг("tree")
  дерево.корень.записатьXml(xml)
  xml.закрытьТэг("tree")

функ Развилка.записатьXml(xml : XmlПисатель)
  xml.открытьТег("node")
  xml.атрибут("question", вопрос)
  xml.открытьТэг("yes")
  да.записатьXml(xml)
  xml.закрытьТэг("yes")
  xml.открытьТэг("no")
  нет.записатьXml(xml)
  xml.закрытьТэг("no")
  xml.закрытьТэг("node")

функ Ответ.записатьXml(xml : XmlПисатель)
  xml.открытьТег("answer")
  xml.атрибут("value", результат)
  xml.закрытьТэг("answer")

Чтение будет такое (считаем, что читатель потоковый, автоматически пропускает всё внутри тэга, если не дать команду «войти в тэг», в закончившемся тэге ничего не выводит, пока не дать команду «выйти из тэга», и нет никаких препятствий к тому, чтобы собирать дерево в отрыве от корня).

функ считатьУзел(xml : XmlЧитатель) : узел
  тэг := xml.считатьТэг
  в_зависимости_от (тэг)
    если "node":
      узел := новый Развилка
      узел.вопрос = …
      xml.войтиВТэг

      xml.затребоватьТэг("yes")
      xml.войтиВТэг
      узел.да = считатьУзел(xml)
      xml.выйтиИзТэга

      xml.затребоватьТэг("no")
      xml.войтиВТэг
      узел.нет = считатьУзел(xml)
      xml.выйтиИзТэга

      xml.выйтиИзТэга
      верни узел
    если "answer":
      узел := новый Ответ
      узел.результат = …
      верни узел
    иначе:
      ошибка

функ Дерево.считатьXml(xml : XmlЧитатель)
  xml.затребоватьТэг("tree")
  xml.войтиВТэг
  узел := считатьУзел(xml)
  xml.выйтиИзТэга
  установитьКорень(узел)

В учебной задаче — пометить каждый узел (вопрос или ответ), примерно так.

Q
У него есть колёса?
A
наркоман
Q
Он живёт в лесу?
…

Опять-таки, возможен двоичный аналог. Код точно такой же, только команды «войти/выйти» не нужны.

Ах да. У вас в тэгах написано «Си». Скажите хоть, каким образом вы налаживаете указатели на два разных типа узлов (ответы и развилки), и мы придумаем, как это сделать. Например, если ответ — это та же развилка, только без обоих сыновей…

функ записатьXml(xml, узел)
  если узел.да≠⌀ и узел.нет≠⌀
    ветвь_для развилки
  иначе если узел.да=⌀ и узел.нет=⌀
    ветвь_для_ответа
  иначе ошибка

Comments

[Алексей Майрин]

На самом деле, хотелось бы понять именно на си, и именно логику хранения дерева в файле, а не через xml документы, если что-то знаете могли бы подсказать по этому поводу, было бы очень круто!)

[Mercury13]

А XML-документ разве не файл?
Допустим, есть такое дерево.

у него есть колёса?
  +: он пыхтит косячком?
    +: наркоман
    −: трактор
  −: кот

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

В учебном коде можно попроще: либо «Q вопрос узел+, узел−», либо «A ответ». То есть:

Q
у него есть колёса?
Q
он пыхтит косячком?
A
наркоман
A
трактор
A
кот

Node* readNode(FILE* file)
{
  char c[…];
  readLine(file, c);
  switch (c[0]) {
  case 'Q': {
      Node* node = malloc(…);
      readLine(file, node.text);
      Node.yes = readNode(file);
      Node.no = readNode(file);
      return node;
    }
    case 'A': {
      Node* node = malloc(…);
      readLine(file, node.text);
      Node.yes = NULL;
      Node.no = NULL;
      return node;
    }
    default: ; // ошибка
  }
}

Функцию readLine описывать не буду. Принцип легко переносится на двоичный файл. Хотя этот принцип не столь расширяем, как XML.

[Алексей Майрин]

Mercury13: океей, спасибо большое за наводку, уже на самом деле Понял, что через хмл лучше даже попробовать сделать, большое спасибо!)

[Mercury13]

Алексей Майрин: Разумеется, придётся найти Си-библиотеку поддержки XML.