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

 1 #include <iostream.h>
 2 
 3 struct BSTreeNode
 4 {
 5     int m_nValue;
 6     struct BSTreeNode *m_pLeft;
 7     struct BSTreeNode *m_pRight;
 8 };
 9 
10 void addBSTreeNode(BSTreeNode *&pCurrent,int value); //建立二叉排序树
11 void inOrderBSTree(BSTreeNode *pBSTree); //中序遍历
12 void convertToDoubleList(BSTreeNode *pCurrent);//转换成双链表
13 
14 BSTreeNode *pHead=NULL;//指向双链表的头结点
15 BSTreeNode *pIndex=NULL;//指向前一个结点
16 
17 int main()
18 {
19     BSTreeNode *pRoot=NULL;
20     addBSTreeNode(pRoot,10);
21     addBSTreeNode(pRoot,6);
22     addBSTreeNode(pRoot,14);
23     addBSTreeNode(pRoot,4);
24     addBSTreeNode(pRoot,8);
25     addBSTreeNode(pRoot,12);
26     addBSTreeNode(pRoot,16);
27 
28     inOrderBSTree(pRoot);
29     return 0;
30 }
31 
32 
33 void addBSTreeNode(BSTreeNode *&pCurrent,int value)
34 {
35     if(pCurrent==NULL)
36     {
37         BSTreeNode *pBSTree=new BSTreeNode;
38         pBSTree->m_nValue=value;
39         pBSTree->m_pLeft=NULL;
40         pBSTree->m_pRight=NULL;
41         pCurrent=pBSTree;
42     }
43     else if (pCurrent->m_nValue<value)
44     {
45         addBSTreeNode(pCurrent->m_pRight,value);
46     }
47     else if (pCurrent->m_nValue>value)
48     {
49         addBSTreeNode(pCurrent->m_pLeft,value);
50     }
51     else
52     {
53         cout<<"node repeated"<<endl;
54     }
55 }
56 
57 void inOrderBSTree(BSTreeNode *pBSTree)
58 {
59     if (NULL==pBSTree)
60     {
61         return;
62     }
63 
64     if (NULL!=pBSTree->m_pLeft)
65     {
66         inOrderBSTree(pBSTree->m_pLeft);
67     }
68 
69     convertToDoubleList(pBSTree);
70 
71     if (NULL!=pBSTree->m_pRight)
72     {
73         inOrderBSTree(pBSTree->m_pRight);
74     }
75 }
76 
77 
78 void convertToDoubleList(BSTreeNode *pCurrent)
79 {
80     pCurrent->m_pLeft=pIndex;
81 
82     if (NULL==pIndex)
83     {
84         pHead=pIndex;
85     }
86 
87     else
88     {
89         pIndex->m_pRight=pCurrent;
90     }
91 
92     pIndex=pCurrent;
93 
94     cout<<pCurrent->m_nValue<<" ";
95 }