將鏈接列表轉換爲二叉搜索樹？

Question

鑑於圓雙向鏈表...我怎樣才能轉換成二叉搜索樹..

的問題是在 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; 
} 

Answer 1

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; 
}