Как я могу прочитать и оценить двоичный файл, в котором хранится двоичное дерево поиска? - PullRequest
Новая
       38

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

0 голосов
/ 29 марта 2020

У меня есть двоичный файл, и я хочу оценить, имеет ли оно двоичное дерево поиска и сбалансировано ли оно по высоте. Структура: 

struct node {
int val;
char bal;
struct node *left;
struct node *right;
}

И она сохраняется в обходе предзаказа. Предполагается, что символ представляет собой двоичный шаблон, где в нулевой позиции бита 0-бит означает, что правая ветвь узла равна NULL. 1-бит означает, что правая ветвь узла является ненулевым узлом. В позиции бита 1 (вторая наименее значимая битовая позиция) 0-бит означает, что левая ветвь узла имеет значение NULL. 1-бит означает, что левая ветвь узла не является NULL. Бинарное значение 2 или 3 означает, что есть левый потомок. Двоичное значение 1 или 3 означает, что есть правильный ребенок. У меня есть пример текстового представления двоичного файла: 

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

Где 3 представляет, что узел имеет двух дочерних элементов, 2 представляет, что узел имеет только левого дочернего элемента, 1 представляет, что узел имеет только правый ребенок, а 0 ноль детей. Если я строю дерево (помня, что это обход по предварительному заказу), я получаю это: 

          -2
        /      \ 
       -4        2
     /   \      /  \ 
    -5   -3    0     5
              /  \     \
             -1   1     4

Это дерево не является двоичным деревом поиска, так как 5 больше 4. Но оно сбалансировано. Учитывая фактический двоичный файл, который является этим (используя команду xxd -b): 

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

Как на самом деле открыть двоичный файл и выполнить этот вид оценки? где я могу оценить, действительно ли это BST и сбалансирован ли он по высоте? Я изо всех сил пытаюсь начать просто потому, что входной файл является двоичным, и я не знаю, как пройти через это.

...