1.把二元查找树转变成排序的双向链表

参照了别人的代码，自己写一遍，好好理解下
View Code
 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct BSTreeNode
 5 {
 6     BSTreeNode *m_pLeft;
 7     BSTreeNode *m_pRight;
 8     int m_Value;
 9 };
10 
11 BSTreeNode *phead;
12 BSTreeNode *pnext;
13 
14 void converttoDoubleList(BSTreeNode *pCurrent)     //结点链表化
15 {
16     pCurrent->m_pLeft = pnext;
17     if(NULL==pnext)
18     {
19         phead=pCurrent;
20     }
21     else
22     {
23         pnext->m_pRight = pCurrent;
24     }
25     pnext = pCurrent;
26     cout<<pCurrent->m_Value<<endl;
27 }
28 
29 //加入结点，建立二元查找树
30 void AddNodeToTree(BSTreeNode * &pCurrent,int value)
31 {
32     if(NULL==pCurrent)
33     {
34         BSTreeNode *pTree = new BSTreeNode();
35         pTree->m_pLeft = NULL;
36         pTree->m_pRight = NULL;
37         pTree->m_Value = value;
38         pCurrent = pTree;
39     }
40     else if(pCurrent->m_Value > value )
41     {
42         AddNodeToTree(pCurrent->m_pLeft,value);
43     }
44     else if(pCurrent->m_Value < value )
45     {
46         AddNodeToTree(pCurrent->m_pRight,value);
47     }
48 }
49 
50 //中序遍历二元查找树
51 void InOrderTraverse(BSTreeNode *pCurrent)
52 {
53     if(NULL==pCurrent)
54     {
55         return ;
56     }
57     if(NULL!=pCurrent->m_pLeft)
58     {
59         InOrderTraverse(pCurrent->m_pLeft);
60     }
61 
62     converttoDoubleList(pCurrent);       //左子树遍历完后，对该指针链表化
63 
64     if(NULL!=pCurrent->m_pRight)
65     {
66         InOrderTraverse(pCurrent->m_pRight);
67     }
68 }
69 
70 int main()
71 {
72     BSTreeNode *pstart = NULL;
73     phead = pnext = NULL;
74 
75     AddNodeToTree(pstart,10);
76     AddNodeToTree(pstart,16);
77     AddNodeToTree(pstart,14);
78     AddNodeToTree(pstart,12);
79     AddNodeToTree(pstart,4);
80     AddNodeToTree(pstart,8);
81     AddNodeToTree(pstart,6);
82     
83     InOrderTraverse(pstart);
84 
85     return 0;
86 }