c++ - 如何将二叉搜索树转换为双向链表？

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

这是一种广度优先搜索算法。 Wikipedia对如何实现它有很好的解释。

实现算法后，创建链表应该很简单(因为只需将每个访问的元素附加到列表中即可)