соединяют узлы на одном уровне двоичного дерева

Question

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

Ради обсуждения, давайте рассмотрим дерево как:

   0 
      1  2 
     3  4 5 6 
    7      9 

В вышеописанном случае:

0 should point to null. 
1 should point to 2. 
3 should point to 4. 
.... 
7 should point to 9. 
9 should point to NULL. 

Базовая структура дерева:

class Tree { 
    public: 
    int data; 
    Tree* left; 
    Tree* right; 
    Tree* next; 
} 

Answer 1

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

1. Первый уровень уже подключен (он имеет только один узел)

2. Скажем, уровень i подключен. Затем подключить уровень i+1 сделать следующее:

   а) Инициализировать узел lst (только промежуточный переменных мы будем использовать позже) к null

   б) Начало в первом узле на уровне i.

   c) Перемещение узлов на уровне i, начиная с первого узла. Обратите внимание, что вы можете легко перемещать узлы на уровне i, потому что он уже подключен, поэтому у вас есть указатели на сестры в каждом узле.

   d) Для каждого узла на уровне i сначала посмотрите на его левое дочернее устройство, а затем на его правый ребенок. Для каждого ребенка, который не является нулевым, если lst не является null, подключите lst к этому ребенку. Затем установите lst этому ребенку.

Как только вы подключили уровень i + 1, вы можете перейти на следующий уровень. Если после пересечения уровень lst по-прежнему равен нулю, это означает, что ни один узел на этом уровне не имел ребенка => это был последний уровень, вы можете остановить алгоритм.

Легко показать, почему это работает, оно требует линейного времени и постоянного пространства, поэтому оно строго лучше, чем BFS с очередью (которая принимает линейную память).

Answer 2

Использование BFS как предложено в комментариях. Тогда у вас будет расстояние от каждого узла от корня.

псевдо-код:

vis[1..n] = false // mark each node as un-visited 
dis[1..n] = 0 
Queue q 
dis[root] = 0 
vis[root] = true 
q.push(root) 
while !q.empty() 
    node x = q.front() 
    children[] = children nodes of node x 
    for each child in children 
      !vis[child] 
      dis[child] = dis[x] + 1 
      vis[child] =true 
      q.enqueue(child) 
    q.pop() 

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

Answer 3

После идеи Ишамаэль, я хотел бы предложить процедуру вдоль линий

void link_levels(Tree* t){ 
    Tree *head, *tail, *end_of_row; 
    assert (t != 0); 
    t->next = 0; 
    head = tail = end_of_row = t; 
    while(head != 0){ 
     if(head->left != 0){ 
      tail->next = head->left; 
      tail = tail->next; 
      tail->next = 0; 
     } 
     if(head->right != 0){ 
      tail->next = head->right; 
      tail = tail->next; 
      tail->next = 0; 
     } 
     if(head == end_of_row){ 
      head = head->next; 
      end_of_row->next = 0; 
      end_of_row = tail; 
     } 
     else { 
      head = head->next; 
     } 
    } 
}