如何将二叉搜索树转换为双向链表？ [英] How to convert a binary search tree into a doubly linked list?

问题描述

给定一个二叉搜索树，我需要将其转换为双向链表（通过以之字形顺序遍历），只使用指向C ++中的结构的指针，如下所示：

Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows,

给定树：

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

节点结构：

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

创建列表（曲折顺序）：

Create List(zig zag order):

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

有人可以帮我。

推荐答案

这是一个宽度优先的搜索算法。 维基百科对如何实施它有一个很好的解释。

This is a Breadth-first search algorithm. Wikipedia has a good explanation on how to implement it.

在实现算法后，创建你的链表应该是一个没有脑子的（因为它只是一个问题，每个被访问的元素添加到列表）

After implementing the algorithm, creating your linked list should be a no-brainer (since it will only be a matter of appending each visited element to the list)

这篇关于如何将二叉搜索树转换为双向链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！