Как преобразовать двоичное дерево поиска в двусвязный список?

Question

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

Дано дерево:

                1
                |
        +-------+---------+
        |                 |
        2                 3
        |                 |
   +----+---+        +----+---+
   |        |        |        |
   4        5        6        7
   |        |        |        |
+--+--+  +--+--+  +--+--+  +--+--+
|     |  |     |  |     |  |     |
8     9  10    11 12    13 14    15

Структура узла:

struct node
{
    char * data;
    node * left;
    node * right;
};

Создать список (зигзагообразный порядок):

1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8

Может кто-нибудь, пожалуйста, помогите мне.

Answer 1

Это (http://cslibrary.stanford.edu/109/TreeListRecursion.html) имеет ответ с красивыми картинками:)