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

问题描述

给出一个二叉搜索树，我需要使用C ++中的结构指针将它转换成双向链表（以zig zag顺序遍历），

给定树：

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

节点结构：

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

创建列表（zig zag order）：

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

有人可以帮助我。

解决方案

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

在实现算法之后，创建链接列表应该是一个无脑的（因为它只是将每个被访问的元素附加到列表中的问题）

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,

Given Tree:

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

Node Structure:

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

Create List(zig zag order):

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

Could someone please help me out.

解决方案

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屋！