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

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

请问有人能帮我解决问题吗？

- josh

---

链表中节点的顺序是否重要？ - Nick Dandoulakis

那个“创建列表”的部分是答案吗？我不明白他们如何获得或想要那个列表。如果结果是一个列表（1 2 3 4 ... 15），那么更有意义。或者这只是一个层次遍历，每个层次从相反的端点开始？ - Kizaru

@Nick：是的，我已经知道如何创建一个排序列表了。但在这里，我需要按照特定的顺序创建。 - josh

似乎是一种之字形顺序。你应该在问题中提到这一点。 - Nick Dandoulakis

在实现BFS时，您可以使用堆栈和队列。我认为那应该可以工作。 - Arjit

Answer 1

这是一个广度优先搜索算法。Wikipedia上有一个很好的解释，介绍如何实现它。

在实现算法之后，创建你的链表应该很简单（因为只需要将每个访问过的元素附加到列表中）。

- Gustavo Muenz

---

我来发表这个。这就是正确的答案（事实上，维基页面中的图片几乎与他树的图片完全相同！）树只不过是图形 :) - Oren Mazor

这并不是真正的之字形遍历。BFS 沿着相同方向遍历每个级别，而问题明确指出您需要沿着与上一级别相反的方向遍历每个级别。 - David Rodríguez - dribeas

我会像建议的那样进行广度优先搜索，然后使用splice成员来反转每一行的其他行。 - Mooing Duck

Answer 2

这是一种尴尬的树遍历方式。我想知道在实际代码中有多少人真正需要这样做。尽管如此，这就是要解决的问题...

以下是我的处理方法：

首先，当我将期望的输出与树的结构进行比较时，我注意到每个“级别”的树都会从上到下依次处理。因此，首先处理顶部节点，然后处理所有子节点，然后处理所有孙子节点，依此类推。因此，一个循环可以处理一个级别，并同时建立一个下一级别节点列表，以供下一次循环迭代使用。

其次，这个“之”字形的顺序意味着它需要交替处理子节点的方向。如果特定迭代从左到右进行，则下一次迭代必须从右到左进行。然后对于随后的迭代，再次从左到右。因此，在我设计的循环中，处理一个级别并建立下一级别节点列表时，它可能需要具有某种交替行为。在偶数迭代中，列表是按一种方式构建的。在奇数迭代中，列表是按另一种方式构建的。

或者，考虑整个过程的另一种方式是：设计一个可以按1,2,3,4,5,6等顺序构建结果列表的解决方案。然后修改该设计以具有之字形顺序。

这个方案的设计足够详细了吗？

- TheUndeadFish

---

进行层次遍历，然后修改列表并不是通用的方法；对于不完全平衡的二叉搜索树，它将失败。 - Kizaru

Answer 3

在下面的解决方案中，我使用了两个栈来交替存储级别。比如，层次为0的节点将存储在栈1(head1)中；现在当它不为空时弹出元素并将元素推入到栈2中，插入的左右子节点的顺序取决于级别，并且在每个级别改变插入顺序。

node * convert_to_dll(node *p)
{   
    static  int level=0;
    push_in_stack(p,&head1);
    printf("%d\n",p->data);

    while( head1!=NULL || head2!=NULL) {
        //pop_from_queue(&headq);

        if(head1!=NULL && head2==NULL) {
            while(head1!=NULL) {
                if(level%2==0) {
                    node *p;
                    p=new node;
                    p=pop_from_stack(&head1);

                    if(p->right!=NULL) {
                        push_in_stack(p->right,&head2);
                        printf("%d\n",(p->right)->data);
                    }
                    if(p->left!=NULL)
                    {   
                        push_in_stack(p->left,&head2);
                        printf("%d\n",(p->left)->data);
                    }
                }
            }
            //traverse_stack(head2);
            level++;
        } else {
            while(head2!=NULL) {
                if(level%2!=0) {
                    node *q;
                    q=new node;
                    q=pop_from_stack(&head2);

                    if(q->left!=NULL) {
                        push_in_stack(q->left,&head1);
                        printf("%d\n",(q->left)->data);
                    }
                    if(q->right!=NULL) {
                        push_in_stack(q->right,&head1);
                        printf("%d\n",(q->right)->data);
                    }
                }
            } //traverse_stack(head2);
            level++;
        }
    }
    return p;
}

- Pankaj Nayak

---

赞同使用双栈的想法，但实现中有细节需要注意。您不需要跟踪“level”，可以删除依赖它的变量和“if”语句。您正在泄漏内存，“q = new node; q = pop_from_stack(&head);”将创建一个节点并在下一条语句中泄漏它。 - David Rodríguez - dribeas

Answer 4

这可能会对你有所帮助：

2. 为每个树级别创建一个单独的列表
3. 遍历树并在遍历树时将值复制到列表中
4. 反转每个其他列表的顺序
5. 连接这些列表

- Gabriel Schreiber

Answer 5

你可以编写一个函数来在双向链表中添加节点。然后在遍历树的同时调用此函数。通过这种方式，你应该能够完成它。

- easysid

---

@ Edison, Prabhu。我认为树的BFS不会给出问题中完全正确的结果。因为树的BFS将产生以下结果之一：1-2-3-4-5-6-7-8-.....-15或1-3-2-7-6-5-4-15-...8（取决于您是先将右子节点入队还是左子节点）......因此，您列表的中间部分不会由BFS给出。 - easysid

Answer 6

嗯......这个有点难。按照此顺序遍历的问题在于您要跳来跳去。这通常适用于不是深度或广度优先的任何树遍历顺序。

以下是我解决问题的方法。从一个空的节点列表数组开始，深度优先遍历树。一定要记录遍历的深度。

在遍历的每个节点处，注意遍历的深度并选择数组中的索引处的列表。如果没有，请先添加一个。如果深度是偶数（假设根节点的深度为0），则将节点添加到列表的末尾。如果它是奇数，则添加到开头。

遍历所有节点后，请连接列表。

- SingleNegationElimination

Answer 7

为什么要使用指针？你可以将BST存储为数组A[1...n]。因此，A[1]将具有根节点，A[2]和A[3]将具有深度1的节点，以此类推。这是可能的，因为它是一个几乎完整的树，而且您知道在给定深度上将存在多少元素 - 即深度d处的2^d个元素（当然除了最后一层）。现在，您只需要以zig-zag方式访问数组，并创建新的BST（数组）以进行新的排序。那么，如何以zig-zag方式遍历数组呢？对于任何给定元素A[i]，左子节点将是A[2i]，右子节点将是A[2i + 1]。因此，如果当前深度d为奇数，则遍历2^d个元素，并在到达第2^d个元素时转到其左子节点。如果当前深度d为偶数，则再次遍历2^d个元素，但在到达第2^d个元素时，转到其右子节点。将它们存储为数组而不是节点使您的数据结构更加简洁，实现更加简单。

- Chandini David

Answer 8

#include<iostream>
#include<conio.h>
using namespace std;

class TreeNode
{
public:
    int info;
    TreeNode* right;
    TreeNode* left;
    //TreeNode* parent;
    TreeNode()
    {
        info = 0;
        right = left = NULL;
    }

    TreeNode(int info)
    {
        this -> info = info;
        right = left = NULL;
    }
};

class ListNode
{
public:
    int info;
    ListNode* next;
    ListNode()
    {
        info = 0;
        next = NULL;
    }

    ListNode(int info)
    {
        this -> info = info;
        next = NULL;
    }
};

TreeNode* root = NULL;
ListNode* start;
ListNode* end;

void addTreeNode(TreeNode*);
void convertTreeToList(TreeNode*);
void printList(ListNode*);
int findDepth(TreeNode*);

int _tmain(int argc, _TCHAR* argv[])
{
    start = end = new ListNode(0);
    char choice = 'y';
    int info;
    while(choice == 'y')
    {
        cout<<"Enter the info of new node:\n";
        cin>>info;
        addTreeNode(new TreeNode(info));
        cout<<"Want to add a new node to the tree?(y/n)\n";
        cin>>choice;
    }

    cout<<"Depth of the tree is: "<<findDepth(root);

    cout<<"Converting the tree into a doubly linked list....\n";

    convertTreeToList(root);
    printList(start->next);
    cin>>choice;
    return 0;
}



void addTreeNode(TreeNode* node)
 {
     if(!root)
     {
         root = node;
     }
     else
     {
         TreeNode* currRoot = root;
         while(1)
         {
             if(node -> info >= currRoot -> info)
             {
                 if(!currRoot -> right)
                 {
                     currRoot -> right = node;
                     break;
                 }
                 else
                 {
                     currRoot = currRoot -> right;
                 }
             }
             else
             {
                 if(!currRoot -> left)
                 {
                     currRoot -> left = node;
                     break;
                 }
                 else
                 {
                     currRoot = currRoot -> left;
                 }
             }
         }
     }
 }

 void convertTreeToList(TreeNode* node)
 {
     if(node -> left != NULL)
     {
         convertTreeToList(node -> left);
     }

         end ->next = new ListNode(node -> info);
         end = end -> next;
         end -> next = start;



         if(node -> right != NULL)
     {
         convertTreeToList(node -> right);
     }

 }


 void printList(ListNode* start)
 {
     while(start != ::start)
     {
         cout<<start->info<<" -> ";
         start = start -> next;
     }
     cout<<"x";
 }

 int findDepth(TreeNode* node)
 {
     if(!node)
     {
         return 0;
     }
     else
     {
         return (max(findDepth(node -> left), findDepth(node -> right)) + 1);
     }
 }

这里提供的链表是单向链表且已排序。希望您可以轻松地修改此代码以获得双向链表。只需复制-粘贴此代码并编译即可，它将正常工作。

- Rampal Chaudhary

Answer 9

假设二叉树的根节点位于第0层（一个偶数）。连续的层可以看作是奇偶交替的（根节点的子节点在奇数层，它们的子节点在偶数层等等）。对于一个在偶数层的节点，我们将其子节点推入堆栈中（这使得反向遍历成为可能）。对于一个在奇数层的节点，我们将其子节点推入队列中（这使得正向遍历成为可能）。在子节点被推入后，我们移除下一个可用元素（堆栈的顶部或队列的前端），并通过改变级别到奇数或偶数来递归调用函数，具体取决于已移除元素的位置。已移除的元素可以插入到双向链表的末尾。伪代码如下。

// S = stack [accessible globally]
// Q = queue [accessible globally]
//    
// No error checking for some corner cases to retain clarity of original idea    
void LinkNodes(Tree *T,bool isEven,list** l)
{

     if(isEven) {
        S.push(T->right);
        S.push(T->left);
        while( !S.empty() ) {
             t = S.pop();
             InsertIntoLinkedList(l,t);
             LinkNodes(t,!isEven);
        }
     } else {
        Q.enque(T->left);
        Q.enque(T->right);
        while( !Q.empty() ) {
            t = Q.deque();
            InsertIntoLinkedList(l,t);
            LinkNodes(t,isEven);
        }
     }
}

在调用函数中：

bool isEven = true;
list *l = NULL;           
// Before the function is called, list is initialized with root element
InsertIntoLinkedList(&l,T); 

LinkNodes(T,isEven,&l);

- curryage

Answer 10

这个 (http://cslibrary.stanford.edu/109/TreeListRecursion.html) 有非常漂亮的图片来解答 :)

- Rohan Monga

---

该链接是树的顺序遍历，而不是之字形遍历。 - David Rodríguez - dribeas