Создание бинарного дерева

Question

Я дал Linked List Представление полного двоичного дерева в формате следующим образом:

Я должен преобразовать связанный список для завершения двоичных tree.I я использую очередь сделать то же самое. Я сохраняю корневой каталог в очереди, сохраняя его в переменной, указывающей на новый узел, который я создаю, а затем сохраняю левый и правый указатели и делаю это снова, но я получаю только один узел как вывод, когда обход предварительных заказов выполняется на самодельном дереве. Например. Связанный список - 1-> 2-> 3-> 4-> 5-> NULL, но при обходе предварительного заказа я получаю 1 в качестве вывода.

void convert(node *head,TreeNode * &root) 
{ 
    if(head==NULL){ 
     root=NULL; 
     return; 
    } 
    queue<struct TreeNode* >Q; 
    Q.push(root);  // Pushing root which is Null at start. 
    while(head!=NULL){ 
     struct TreeNode * x=Q.front();  // storing 
     Q.pop();     //Popping 
     x=new TreeNode;   //pointing this null pointer to a new node 
     x->data=head->data;  // storing data 
     x->left=NULL;   //Making left of this point to NuLL 
     x->right=NULL;   //Making right of this point to NuLL 
     if(!root)root=x;  // If root is null point it to x. 
     Q.push(x->left);  // Push the left child pointer which is NULL 
     Q.push(x->right);  // Push the right child pointer which is NULL 
     head=head->next; // Move further in linked list. 
    } 
    } 

Answer 1

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

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

queue<struct TreeNode* >Q;   // Q: [] 
Q.push(root);      // Q: [NULL] 
while(head!=NULL){ 
    struct TreeNode * x=Q.front(); // x = NULL, Q: [NULL] 
    Q.pop();      // Q: [] 
    x=new TreeNode;     // x: -> TreeNode {} 
    x->data=head->data;    // 
    x->left=NULL;     // 
    x->right=NULL;     // x: ->TreeNode {data: data of initial head, 
            //    left: NULL, right:NULL} 
    if(!root)root=x;    // root: ->TreeNode {data: data of initial head, 
            //     left: NULL, right:NULL} 
    Q.push(x->left);    // Q: [NULL] 
    Q.push(x->right);    // Q: [NULL, NULL] 
    head=head->next;    // Move further in linked list. 
} 
{ 
    struct TreeNode * x=Q.front(); // x = NULL, Q: [NULL, NULL] 
    Q.pop();      // Q: [NULL] 
    x=new TreeNode;     // x: -> TreeNode {} 
    x->data=head->data;    // 
    x->left=NULL;     // 
    x->right=NULL;     // x: ->TreeNode {data: head->data, left: NULL, right:NULL} 
    if(!root)root=x;    // root: still ->TreeNode {data: data of initial head, 
            //       left: NULL, right:NULL} 
    Q.push(x->left);    // Q: [NULL, NULL] 
    Q.push(x->right);    // Q: [NULL, NULL, NULL] 
    head=head->next;    // Move further in linked list. 
} 
{ 
    struct TreeNode * x=Q.front(); // x = NULL, Q: [NULL, NULL, NULL] 
    Q.pop();      // Q: [NULL, NULL] 
    x=new TreeNode;     // x: -> TreeNode {} 
    x->data=head->data;    // 
    x->left=NULL;     // 
    x->right=NULL;     // x: ->TreeNode {data: head->data, left: NULL, right:NULL} 
    if(!root)root=x;    // root: still ->TreeNode {data: data of initial head, 
            //       left: NULL, right:NULL} 
    Q.push(x->left);    // Q: [NULL, NULL, NULL] 
    Q.push(x->right);    // Q: [NULL, NULL, NULL, NULL] 
    head=head->next;    // Move further in linked list. 
} 

Как вы можете видеть, вы нажимаете и вставляете ряд нулевых указателей в очередь.
Вы никогда не используете значения из очереди ни для чего.

Для выяснения вопроса, предположим, что вы имели очереди целых чисел и сделал это:

struct S { int x; }; 
S s; 
s.x = 0; 
queue<int> q; 
q.push(s.x); 
int y = q.front(); 
y = 96; 

Я уверен, что вы не ожидали бы значение s.x внезапно стать 96 вместо 0.
Указатели работают точно так же.

Вы также никогда не изменяете созданный вами корневой узел, поэтому вы получаете только одноузловое дерево (другие узлы - это просто утечки памяти).

Вы можете

• Поп указатель узла дерева
• Получить следующие два элементов из списка (если они существуют)
• Сделать новые узлы из элементов списка в качестве соответствующего
• Установите левый и правый указатели вытолкнутого узла на эти два новых.
• Вставьте новые указатели в очередь
• Repeat