把二元查找樹轉變成排序的雙向鏈表

[cpp]
<span style="color: rgb(51, 51, 51); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>把二元查找樹轉變成排序的雙向鏈表 
</strong>題目： 
輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。 
要求不能創建任何新的結點，只調整指針的指向。 
   
   10 
   / / 
  6  14 
/ / / / 
4  8 12 16 
   
轉換成雙向鏈表 
4=6=8=10=12=14=16。</span> 
[cpp] 
#include <iostream> 
using namespace std; 
 
class Node{ 
public: 
    int data; 
    Node *left; 
    Node *right; 
     
    Node(int d = 0, Node *lr = 0, Node *rr = 0):data(d), left(lr), right(rr){} 
}; 
 
Node *create() 
{ 
    Node *root; 
    Node *p4 = new Node(4); 
    Node *p8 = new Node(8); 
    Node *p6 = new Node(6, p4, p8); 
     
    Node *p12 = new Node(12); 
    Node *p16 = new Node(16); 
    Node *p14 = new Node(14, p12, p16); 
 
    Node *p11 = new Node(11); 
    Node *p13 = new Node(13); 
    p12->left = p11; 
    p12->right = p13; 
 
    Node *p15 = new Node(15); 
    Node *p19 = new Node(19); 
 
    Node *p18 = new Node(18); 
    Node *p20 = new Node(20); 
    p16->left = p15; 
    p16->right = p19; 
     
    p19->left = p18; 
    p19->right = p20; 
    Node *p10 = new Node(10, p6, p14); 
    root = p10; 
     
    return root; 
} 
 
void BTreeToLink(Node* &node,int curIndex) 
{ 
    Node* ptr; 
    if (node->left) 
    { 
        BTreeToLink(node->left,curIndex+1); 
        node->left->right = node; 
    } 
    if (node->right) 
    { 
        BTreeToLink(node->right,curIndex+1); 
 
        ptr = node->right; 
        while(ptr->left) //移向值最小的節點 
            ptr = ptr->left; 
        ptr->left = node; //將節點連接起來 
        node->right = ptr; 
        while(node->right) //指向最大的節點 
            node = node->right;           
    } 
} 
int main(int argc, char* argv[]) 
{ 
 
    Node *root = create(); 
    Node *ptr = NULL; 
    BTreeToLink(root,0); 
 
    ptr = root; 
    while (ptr->left!=NULL) 
    { 
        ptr = ptr->left; 
    } 
 
    while(ptr) 
    { 
        cout<<ptr->data<<endl; 
        ptr = ptr->right; 
    } 
    return 0; 
}