1 // 题目： 2 // 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 3 // 要求不能创建任何新的结点，只调整指针的指向。 4    5 //    10 6 //    / / 7 //   6  14 8 // / / / / 9 // 4  8 12 1610   11 // 转换成双向链表12 // 4=6=8=10=12=14=16。13 14 #include <iostream>15 using namespace std;16 17 class Node{18   public:19     int data;20     Node *left;21     Node *right;22 23     Node(int d = 0, Node *lr = 0, Node *rr = 0):data(d), left(lr), right(rr){}24 };25 26 Node *create()27 {28   Node *root;29   Node *p4 = new Node(4);30   Node *p8 = new Node(8);31   Node *p6 = new Node(6, p4, p8);32 33   Node *p12 = new Node(12);34   Node *p16 = new Node(16);35   Node *p14 = new Node(14, p12, p16);36 37   Node *p10 = new Node(10, p6, p14);38   root = p10;39 40   return root;41 }42 43 Node *change(Node *p, bool asRight)44 {45   if (!p)46     return NULL;47   Node *pLeft = change(p->left, false);48   if (pLeft)49     pLeft->right = p;50   p->left = pLeft;51 52   Node *pRight = change(p->right, true);53   if (pRight)54     pRight->left = p;55   p->right = pRight;56 57   Node *r = p;58   if (asRight)59   {60     while (r->left)61       r = r->left;62   }else{63     while (r->right)64       r = r->right;65   }66   return r;67 }68 69 int main(){70   Node *root = create();71   Node *tail = change(root, false);72   while (tail)73   {74     cout << tail->data << " ";75     tail = tail->left;76   }77   cout << endl;78 79   root = create();80   Node *head = change(root, true);81   while (head)82   {83     cout << head->data << " ";84     head = head->right;85   }86   cout << endl;87   return 1;88 }