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

发布时间：2020-12-16 04:54:17 所属栏目：百科来源：网络整理

导读：给定一个二叉搜索树,我需要将它转换为双链表(通过以Z字形顺序遍历),仅使用指向C中结构的指针,如下所示, 鉴于树： 1 | +-------+---------+ | | 2 3 | | +----+---+ +----+---+ | | | | 4 5 6 7 | | | |+--+--+ +--+--+ +--+--+ +--+--+| | | | | | | |8 9 10

给定一个二叉搜索树,我需要将它转换为双链表(通过以Z字形顺序遍历),仅使用指向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

有人可以帮帮我吗.

解决方法

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

在实现算法之后,创建链表应该是明智的(因为它只是将每个访问过的元素附加到列表中)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!