1 struct BSTreeNode
 2 {
 3     int m_value;
 4     BSTreeNode* m_pLeft;
 5     BSTreeNode* m_pRight;
 6 };
 7 
 8 BSTreeNode* convert(BSTreeNode* phead, bool asRight)
 9 {
10     if (!phead)
11         return NULL;
12     BSTreeNode* pLeft = 0, *pRight=0;
13     if (phead->m_pLeft)
14         pLeft = convert(phead->m_pLeft, false);
15     if (pLeft) {
16         pLeft->m_pRight = phead;
17         phead->m_pLeft = pLeft;
18     }
19     if (phead->m_pRight)
20         pRight = convert(phead->m_pRight, true);
21     if (pRight) {
22         pRight->m_pLeft = phead;
23         phead->m_pRight = pRight;
24     }
25     BSTreeNode* ptmp = phead;
26     if (asRight) {
27         while (ptmp->m_pLeft) {
28             ptmp = ptmp->m_pLeft;
29         }
30     } else {
31         while (ptmp->m_pRight) {
32             ptmp = ptmp->m_pRight;
33         }
34     }
35     return ptmp;
36 }
37 
38 BSTreeNode* convert2doublelist(BSTreeNode* phead)
39 {
40     return convert(phead, true);
41 }
42