Как преобразовать данный уровень двоичного дерева поиска в связанную цепочку? - PullRequest
Новая
       41

Как преобразовать данный уровень двоичного дерева поиска в связанную цепочку?

1 голос
/ 13 апреля 2019

Мне нужно сделать функцию, где, учитывая int n и двоичное дерево поиска, мне нужно преобразовать уровень n в bst int в связанный список.например, если задано число 2 и это дерево 

      2
     /  \
    5    3

, мне нужно составить список избранного с 5 - 3

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

так что это структура для bst и связанной цепочки: 

struct nodo {
    info_t dato; 
    nodo *anterior;
    nodo *siguiente;
};
struct rep_cadena {
    nodo *inicio;
    nodo *final;
};
struct rep_binario {
    info_t dato;
    rep_binario *izq;
    rep_binario *der;
};

и это функция, которую я не могу понять: 

cadena_t nivel_en_binario(nat l, binario_t b)

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

nat altura_binario(binario_t b) {
    if (b==NULL) return 0;
    else return maximo(altura_binario(b->izq), altura_binario(b->der))+ 1;
    }

, где maximo () возвращает наибольшее число между двумя заданными числами.

Ответы [ 2 ]

0 голосов
/ 25 апреля 2019

Adivino, Tarea 3 Programacion 2 Fing jajaja, estamos en la misma, pudiste solucionarlo?

0 голосов
/ 13 апреля 2019

Вы можете сделать это, применив алгоритм Breadth-first_search и немного изменив его. Вместо того, чтобы ставить в очередь только узлы, вы можете ставить в очередь пары (node, level) (где уровень узла = родительский уровень + 1), а затем при постановке в очередь вы можете проверить, достигли ли вы требуемого уровня, и просто вывести его как результат вместо постановки в очередь. это дальше.

Эскиз псевдокода: 

target_level = ...read from input...

let level_nodes = ...an empty list...

let queue = ...an empty queue...
queue.enqueue((root_node, 0))

while queue is not empty:
    node, level = queue.dequeue()
    if level == target_level:
        level_nodes.append(node)
    else:
        if node has left child:
            queue.enqueue((left_child_node, level + 1))
        if node has right child:
            queue.enqueue((right_child_node, level + 1))
...