2017-01-17 1 views
0

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

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

   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; 
} 
+0

Вы можете перемещаться по дереву с помощью levelwise [поиск в ширину] (https://en.wikipedia.org/wiki/ Breadth-first_search) Алгоритм и на каждом уровне вы можете временно хранить предыдущий узел. Тогда 'next'' предыдущего узла' будет '' в настоящее время разобранным узлом '. – sameerkn

+0

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

+0

@sameerkn, я это понимаю. Не могли бы вы написать псевдокод? –

ответ

1

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

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

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

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

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

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

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

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

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

+0

Вариант на этом состоит в том, чтобы просто использовать сам узел в качестве элементов очереди, используя их следующий указатель. Нам нужно только сохранить указатель на следующий конец строки, потому что когда конец текущей строки обрабатывается, хвост очереди указывает на конец следующей строки. – Gribouillis

0

Использование 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() 

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

+0

Узлы могут быть связаны друг с другом в одном цикле, потому что они появятся в очереди в порядке 0 1 2 3 4 5 6 7 9. – Gribouillis

1

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

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; 
     } 
    } 
} 
Смежные вопросы