Как конвертировать двусвязного список бинарного дерева

Question

struct cnode 
{ 
    int info; 
    struct cnode *next; 
    struct cnode *previous; 
}; 
typedef struct cnode cnode; 

предварительно сделанные двусвязного LIST: 1<->2<->3<->4<->5<->6<->7

Так что я пытаюсь сделать рекурсивную функцию, которая захватывает середину двусвязного списка (корень = 4) и преобразовать его в оставшееся в двоичное дерево. Я все еще новичок в рекурсии, поэтому объяснение вместе с кодом было бы НАСТОЯТЕЛЬНО оценено!

EX.  4 
    /\ 
    2 6 
    /\/\ 
    1 3 5 7 

Это код, который я до сих пор (что не сильно из-за трудностей с рекурсией)

void *convert(cnode *head){ 
    if(head == NULL) 
    return; 
    int count = 0; 
    cnode *tempHead = head; 
    while(tempHead != NULL){ 
    count++; 
    tempHead = tempHead->next; 
    } 
    int move = (count/2) + (count%2); 
    int i; 
    for(i=1; i<move; i++){ 
    head = head->next; 
    } 
} 

Довольно много просто устанавливает указатель головы к середине информации (4)

Answer 1

Думаю, я понимаю; вы создаете сбалансированное двоичное дерево от cnodes с previous и next указатели повторно используются для левого и правого поддеревьев.

... так что это ваш алгоритм.

• Найдите средний узел двоичного дерева (которое вы уже сделали).
• Поверните левую половину в двоичное дерево. Левая половина - это оригинальная голова, а последний элемент (средний -> предыдущий) теперь имеет следующий указатель NULL.
• Ссылка: Эта левая половина содержит средний-> предыдущий (угнанный как левый поддон).

• Поверните правую половину в двоичное дерево; это возглавляет средний-> следующий. Сделать это новое значение средний-> следующий.

• Вы должны сохранить исходную голову как указатель на левое поддерево.

• Вы хотите, чтобы ваша подпрограмма возвращала корень двоичного дерева, поэтому предыдущий вызов может связать его с уровнем выше.
• Вам все еще нужно выбрать условие завершения, например, указатель на голову NULL.

Это поможет вам перейти к решению?

Answer 2

Во-первых, вы пытаетесь преобразовать DLL в двоичное дерево, предполагая, что DLL задается как порядковый номер бинарного дерева, которое вы должны сделать. Обратите внимание, что нет уникального дерева, которое вы можете сделать только из обходного пути. Даже если вам нужно сделать BST, вы не можете сделать его только с обходным порядком. То, что я на самом деле думаю, что вы пытаетесь сделать, это преобразовать его в сбалансированный BST. Хотя это также не будет уникальным.
Вот алгоритм.
1) Получите среднее из связанного списка и сделайте его root.
2) Рекурсивно сделать то же самое для левой половины и правой половины.
  a) Получите середину левой половины и заставьте ее оставить дочерний корень , созданный на шаге 1.
  b) Получите середину правой половины и сделайте ее правильным дочерним по отношению к корню , созданному на этапе 1.
Сложность времени: O (nLogn), где n - количество узлов в Связанном списке.
Хотя, он может быть решен в O (n), если вы вставляете узлы в BST в том же порядке, что и в Doubly Linked List.