將BST轉換爲排序的雙向鏈表（調試）

Question

這是一個將二叉搜索樹轉換爲排序雙向鏈表的功能。想法是進行一次遍歷並將訪問節點放入一個大小爲2的圓形數組中。然後調整左右指針以轉換爲雙向鏈表。當前節點的右指針從不修改並稍後訪問。問題出在哪裏？

void TreetoQueue(node* tnode) 
{static node* arr[2]={NULL,NULL}; 
    static int index=0; 
    if(tnode==NULL) return; 
    TreetoQueue(tnode->left); 
    arr[index]=tnode;  //current node 
    if(arr[1]!=NULL) 
     { if(index==0) 
     {arr[1]->right=arr[0]; //modify right pointer of inorder predecessor to point to current node 
     arr[0]->left=arr[1]; //modify current node's left pointer to point to inorder predecessor 
     } 

     if(index==1) 
     {arr[0]->right=arr[1]; 
     arr[1]->left=arr[0]; 
     } 
    cout<<"index-"<<index<<" "<<arr[0]->val<<" "<<arr[1]->val<<"\n"; 
    } 

    index=(index+1)%2; 
    TreetoQueue(tnode->right); 
    } 

      _______5______ 
     /   \ 
     ___3__    6__ 
    / \    \ 
    1  4    _9 
         /\ 
          7 10 


index-1 1 3 
index-0 4 3 
index-1 4 5 
index-0 6 5 
index-1 6 7 
index-0 9 7 
index-1 9 10 
node->left->left->right is NULL //Intended to be 3 
node->left->right->left is NULL//intended to be 3 
node->left->right->right is NULL//intended to be 5 

編輯：它可以作爲intended.Only，我不得不改變根開始list.I用於其他功能做this.Could無我有一個額外的功能來實現這一點？

node* TreetoQueue2(node* root) 
     {node* head=root; 
     while(head->left!=NULL) 
     head=head->left; 
     TreetoQueue(root); 
     return head; 
     } 

Answer 1

重申一下丹尼爾說，下面的測試代碼的工作（使用g ++ - 4.7）預期：

#include <iostream> 

using namespace std; 

struct node { 
     node * left; 
     node * right; 
     int val; 
}; 

typedef node * node_ptr; 

void TreetoQueue(node* tnode) { 

     static node* arr[2]={NULL,NULL}; 

     static int index=0; 

     if(tnode==NULL) return; 

     TreetoQueue(tnode->left); 

     arr[index]=tnode;  //current node 

     if(arr[1]!=NULL) 
     { 
       if(index==0) 
       { 
         arr[1]->right=arr[0]; //modify right pointer of inorder predecessor to point to current node 
         arr[0]->left=arr[1]; //modify current node's left pointer to point to inorder predecessor 
       } 

       if(index==1) 
       { 
         arr[0]->right=arr[1]; 
         arr[1]->left=arr[0]; 
       } 
       cout<<"index-"<<index<<" "<<arr[0]->val<<" "<<arr[1]->val<<"\n"; 
     } 

     index=(index+1)%2; 
     TreetoQueue(tnode->right); 
} 

int main(int argc, char *argv[]){ 
     node_ptr np0 = new node(); 
     node_ptr np1 = new node(); 
     node_ptr np2 = new node(); 
     node_ptr np3 = new node(); 
     node_ptr np4 = new node(); 
     node_ptr np5 = new node(); 
     node_ptr np6 = new node(); 
     node_ptr np7 = new node(); 

     np0->val = 5; 
     np1->val = 3; 
     np2->val = 1; 
     np3->val = 4; 
     np4->val = 6; 
     np5->val = 9; 
     np6->val = 7; 
     np7->val = 10; 

     np0->left = np1; 
     np1->left = np2; 
     np1->right = np3; 

     np0->right = np4; 
     np4->right = np5; 

     np5->left = np6; 
     np5->right = np7; 


     TreetoQueue(np0); 


} 

Answer 2

我已經寫了什麼，我認爲是一種更簡單，更優雅的解決方案仍扮演一個遞歸序遍歷的想法，但並不需要在每個呼叫分配任何內存：

Node* Inorder(Node* _n, Node*& _listHead, Node* _lastP=NULL){ 
    if (_n->left) 
    _lastP = Inorder(_n->left, _listHead, _lastP); 
    if (_lastP){ 
    _lastP->right = _n; 
    _n->left = _lastP; 
    }else 
    _listHead = _n; 
    if (_n->right) 
    return Inorder(_n->right, _listHead, _n); 
    return _n; 
} 

的想法是跟蹤被添加到列表中的最後一個元素（_lastP）。在寫入代碼時，代碼將銷燬二叉搜索樹結構而不是已排序的雙鏈表。

下面是完整的代碼：

#include <iostream> 
using namespace std; 
struct Node{ 
    int data; 
    Node* left; 
    Node* right; 
    Node(int _d=0):data(_d),left(NULL),right(NULL){} 
}; 

Node* Inorder(Node* _n, Node*& _listHead, Node* _lastP=NULL){ 
    if (_n->left) 
    _lastP = Inorder(_n->left, _listHead, _lastP); 
    if (_lastP){ 
    _lastP->right = _n; 
    _n->left = _lastP; 
    }else 
    _listHead = _n; 
    if (_n->right) 
    return Inorder(_n->right, _listHead, _n); 
    return _n; 
} 

Node* BSTtoSortedDoublyLinkedList(Node* _treeRoot){ 
    if(!_treeRoot) 
    return NULL; 
    Node* listHead = NULL; 
    Node* listTail = Inorder(_treeRoot, listHead); 
    //could make circular with following lines 
    //listHead->left = listTail; listTail->right = listHead; 
    return listHead; 
} 

int main(){ 
    //create our tree 
    Node* root = new Node(5); 
    Node* n1 = new Node(3); 
    Node* n2 = new Node(1); 
    Node* n3 = new Node(4); 
    Node* n4 = new Node(6); 
    Node* n5 = new Node(9); 
    Node* n6 = new Node(7); 
    Node* n7 = new Node(10); 

    root->left = n1; 
    n1->left = n2; 
    n1->right = n3; 
    root->right = n4; 
    n4->right = n5; 
    n5->left= n6; 
    n5->right = n7; 
    /* 

     _______5______ 
     /   \ 
    ___3__    6__ 
    / \    \ 
    1  4    _9 
         /\ 
          7 10 
    */ 

    Node* linkedList = BSTtoSortedDoublyLinkedList(root); 
    while(linkedList){ 
    cout << linkedList->data << " "; 
    linkedList = linkedList->right; 
    } 
    return 0; 
}