Программа рекурсии Великого Дерева

Question

Я столкнулся с интересной проблемой, называемой Большой проблемой списка деревьев. Проблема заключается в следующим образом:

В заказанного бинарное дерево, каждый узел содержит один элемент данных и «небольшие» и «большие» указатели на суб-деревья .Все узлы в «малый «sub-tree меньше или равно данным в родительском узле. Все узлы в «большом» поддереве больше родительского узла. И круглый двунаправленный список состоит из previous и следующий указатели.

Задача состоит в том, чтобы взять упорядоченное двоичное дерево и переставить внутренние указатели, чтобы сделать из него круглый двунаправленный список. «небольшого» указатель должен играть роль «предыдущего» и «большого» указатель должен играть роль «следующего». Список должен быть организован так, чтобы узлы находились в порядке возрастания. Я должен написать рекурсивную функцию. & Верните указатель на новый список.

Операция должна выполняться в режиме O (n).

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

Как я должен подойти к проблеме? .. Мне просто нужно руководство для решения проблемы !.

Answer 1

Идея заключается в создании метода, который преобразует узел дерева, содержащий поддеревья (дочерние узлы) в цикл. И учитывая узел, который преобразовал детей (например, после возвращения рекурсивных вызовов), вы создаете новый цикл, указав большой указатель (следующий) самого большого узла на самый маленький узел и маленький указатель наименьшего узла на самый большой узел.

не может быть полным, но это будет близко к этому:

tree_node { 
    small 
    large 
} 

convert(node){ 
    //base case 1, if leaf node 
    if node.small == null && node.large == null 
     return (self, self) 

    //recursively convert children 
    if node.small !=null 
     smallest, larger = convert(node.small) 
    else 
     smallest = larger = self 

    if node.large !=null 
     smaller, largest = convert(node.large) 
    else 
     smaller = largest = self 

    //wrap the ends of the chain 
    largest.large = smallest 
    smallest.small = largest 
    //wrap the mid part 
    smaller.small = larger 
    larger.large = small 

    //return pointers to the absolute smallest and largest of this subtree 
    return (smallest, largest) 
} 

//actually doing it 
convert(tree.root) 

Answer 2

если у вас есть простое дерево 3 узлов

B <--- A ---> C 

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

B -> C 
B <- C 

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

Answer 3

Ключ к рекурсивному программированию представить вас уже есть решение.

Итак, у вас уже есть функция recLink(Tree t), которая принимает указатель на дерево, получается, что дерево в двусвязный круговой списка и возвращает указатель на голову списка (в крайний левый) узел:

recLink(n={Node: left, elt, right}) = // pattern match tree to a full node 
    rt := recLink(right);    // already 
    lt := recLink(left);     // have it 
    n.right := rt;  n.left := lt.left;  // middle node 
    lt.left.right := n; rt.left.right := lt;  // right edges 
    lt.left := rt.left; rt.left := n;  
    return lt; 

Завершить с помощью кромки (пустые дочерние ветви и т. Д.).:)