Создание двоичного дерева в порядке уровня от массива

Question

Я работаю над небольшим алгоритмом, который строит двоичное дерево в порядке уровня. Мне задан массив, и я должен использовать значения в нем для построения двоичного дерева в порядке уровня. Пример: arr inarr [5] = {1,2,3,4,5};

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

 1 
    / \ 
    2  3 
/\ /\ 
    4 5 * * 

(* являются NULL) узлы являются основными бинарными узлы с левым и правым указателем и пробел для int, который содержит значение из массива.

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

Answer 1

«Естественный» способ обхода дерева по уровням использует очередь. Таким образом, интуитивно, алгоритм, который делает обратный, может использовать очередь для запоминания следующих обрабатываемых узлов.

Такой алгоритм будет работать со следующими принципами:

1. Корень общего дерева находится в положении 0
2. Очередь q имеет следующие узлы должны быть обработаны
3. Каждый раз, когда мы видим узел, извлекая из очереди, его дети находятся в позициях i и i+1. Обратите внимание, что обход уровня гарантирует это условие. Так
4. Мы помещаем ребенок текущего узла в очереди

Следующий псевдокод строит дерево из массива, содержащим его по уровням обхода

Node * build_from_level_order(int a[], int n) 
{ 
    Queue q; // this is a queue of pointers to nodes 

    Node * root = (Node*) malloc(sizeof(Node)); 
    root->key = a[0]; root->left = root->right = NULL; 
    q.put(root); 

    for (int i = 1; i < n; /* advancing of i is inside */) 
    { 
     Node * p = q.get(); 

     Node * l = (Node*) malloc(sizeof(Node)); 
     l->key = a[i++]; l->left = l->right = NULL; 

     p->left = l; 
     q.put(l); 

     if (i < n) // last level could end in a left node, this test prevents to see an inexistent right node 
     { 
      Node * r = (Node*) malloc(sizeof(Node)); 
      r->key = a[i++]; r->left = r->right = NULL; 
      p->right = r; 
      q.put(r); 
     } 
    } 

    return root; 
}