Здравствуйте!

Есть ли алгоритм преобразования дерева в линейный список. Что я под этим понимаю.

Например, есть дерево

                    1
            2              3
                     4          5
              6        7    8      9

Нужно из него сделать список 1->next=2, 2->next=3, 3->next=4 и.т.д.
т.е. узлы связываются в список последовательно слева направо, опускаясь на уровень вниз с каждым шагом.

Или если не сложно подскажите как это можно реализовать.

Естественно, что можно было бы создавать список изначально по мере добавления узлов в дерева.

Но задача такова, что на вход подается дерево, у которого есть левый и правый дети

например,

struct tree
{
 tree* left_child
 tree* right_child 
 int data
} T;




Это сообщение отредактировал(а) Alexey91 - 21.12.2011, 20:51

Это широко используемый алгоритм, называется flatten.

Немного не то, но по ссылке http://rosettacode.org/wiki/Tree_traversal

Смотреть level order

Как раз то, что нужно