Пытаетесь построить дерево из обхода предварительного заказа, который хранится в двоичном файле?

Question

Пример двоичного файла, который у меня есть:

0000000: 11111011 11111111 11111111 11111111 00000001 11111100  ......
0000006: 11111111 11111111 11111111 00000001 11111101 11111111  ......
000000c: 11111111 11111111 00000001 11111110 11111111 11111111  ......
0000012: 11111111 00000001 11111111 11111111 11111111 11111111  ......
0000018: 00000001 00000000 00000000 00000000 00000000 00000001  ......
000001e: 00000001 00000000 00000000 00000000 00000001 00000010  ......
0000024: 00000000 00000000 00000000 00000001 00000101 00000000  ......
000002a: 00000000 00000000 00000001 00000100 00000000 00000000  ......
0000030: 00000000 00000000                                      ..

Это текстовое представление того же файла, где каждая строка представляет узел:

-5 1
-4 1
-3 1
-2 1
-1 1
 0 1
 1 1
 2 1
 5 1
 4 0

Где первое число является значение узла. И следующее число представляет, сколько дочерних узлов у узла. 0 означает, что нет детей. 1 означает одного правильного ребенка. 2 означает одного левого ребенка. 3 означает двоих детей.

Это структура узла:

struct Tnode {
int key;
char child;
struct Tnode * left;
struct Tnode * right;
} Tnode;

В настоящее время для каждого узла я пытаюсь использовать fread дважды, один для получения ключа int, а затем для получить чарса ребенка. Но как я могу на самом деле построить дерево, если бинарное дерево содержит обратный порядок? Первый узел, с которым мы сталкиваемся, должен быть root. Поскольку рядом с ним стоит 1, у него будет только правильный дочерний элемент (он будет сохранен в char child). Следовательно, следующий узел должен быть правым потомком этого, как и так далее. По сути, в этом примере право продолжает развиваться до тех пор, пока оно не закончится 4. Но у меня возникли проблемы с его построением. Любые советы?

Answer 1

Вы можете решить эту проблему, используя recursion :

Вы создаете функцию process_node, которая принимает один параметр, который является адресом указателя, который должен указывать на новый узел. При первом вызове функции это будет адрес указателя на узел root.

Функция process_node выполняет следующие действия:

1. Распределяет память для одного struct Tnode.
2. Затем он читает int key и char child из файла и записывает эту информацию во вновь распределенную struct Tnode.
3. Затем записывает адрес вновь созданного узла по адресу, который он получил в качестве параметра функции (который при первом вызове функции является адресом указателя на узел root). Таким образом, новый узел теперь правильно связан с деревом.
4. Если у нового узла есть правый дочерний элемент, то функция process_node теперь будет рекурсивно вызывать себя, но параметр функции этого вызова функции будет на этот раз будет адресом его right переменной-члена. Таким образом, вновь вызванная функция будет писать по этому адресу. Если у узла нет правого дочернего элемента, то для переменной right устанавливается значение NULL.
5. Для левого дочернего элемента повторяется шаг 4.
6. Функция возвращает значение.

После возврата всех рекурсивных вызовов функций у вас должно быть полностью построенное двоичное дерево.