将链表转换为二叉搜索树？

Question

将链表转换为二叉搜索树？

3

给定一个循环双向链表...如何将其转换为二叉搜索树？

这个问题可以在以下链接中找到： http://rajeevprasanna.blogspot.com/2011/02/convert-binary-tree-into-doubly-linked.html 我尝试编写相应的代码，但程序出错了！请给出一些建议。此外，如何找到链表的中间节点？请用代码（C或C++代码）讲解，并提供小例子，如果可能的话。

通过阅读我提供的文章（URL），将BST转换为链表是一个不错的练习。我尝试按照同样的原则进行操作，但我的程序出错了...请帮忙...

Node ListToTree(Node head)
{
    if(head == NULL)
        return NULL;

    Node hleft = NULL, hright = NULL;

    Node root = head;

    hleft = ListToTree(head->left);
    head->left = NULL;
    root->left = hleft;

    hright = ListToTree(head->right);
    head->right = NULL;
    root->right = hright;

    return root;
}

- AGeek

8

“循环双向链表”的中间节点是哪个？想一想……” - pmg

需要一个指向原始头部的引用，并确保右侧和左侧不等于它 o.O - Joe

1

嘿！你是指中位数吗？还是指平均数？或者呢？我不是要刻意挑剔。 - Pete Wilson

所以你想从双向链表转换成二叉搜索树，对吗？我只是问一下因为上面那个链接是相反的。无论如何，你可以通过将一个节点的 next 设置为 null 并进行其他调整来打破双向链表中的循环。顺便设置头指针，并沿着链表向下构建你的二叉搜索树。 - Matthew

《编程面试揭秘》对这个问题有很好的解释。 - rkg

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artem Volkhin · Accepted Answer

class Node {
  Node *prev, *next;
  int value;
}

void listToTree(Node * head) {
    if (head == null)
        return;
    if (head->next == head) {
        head->prev = null;
        head->next = null;
        return head;
    }
    if (head->next->next == head) {
        head->prev = null;
        head->next->next = null;
        head->next->prev = null;
        return head;
    }

    Node *p1 = head, *p2 = head->prev;
    while (p1->value < p2.value)
        p1 = p1->next, p2 = p2->prev;
    Node * root = p1;
    root->prev->next = head;
    root->next->prev = head->prev;
    root->prev = listToTree(head);
    root->next = listToTree(root->next);
    return root;
}