题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8
12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：
struct BTNode{
int value;
BTNode *left;
BTNode *right;
};
typedef BTNode BTree;
1 #include <iostream>
2 #include <cassert>
3 #include <stack>
4 using namespace std;
5
6 struct BTNode{
7 int value;
8 BTNode *left;
9 BTNode *right;
10 };
11 typedef BTNode BTree;
12
13 void DestoryLink(BTree *T){
14 BTree *tmp;
15 while(T){
16 tmp=T;
17 T=T->right;
18 delete tmp;
19 }
20 }
21 void PrintTree(BTree *T){
22 if(!T)return;
23 PrintTree(T->left);
24 cout<<T->value<<" ";
25 PrintTree(T->right);
26 }
27
28
29
30 void Insert(BTree *T,BTNode *node){
31 if(!T)return;
32 BTNode *tmp=T,*pre;
33 while(tmp){
34 if(tmp->value > node->value){
35 pre=tmp;
36 tmp=tmp->left;
37 }else if(tmp->value < node->value){
38 pre=tmp;
39 tmp=tmp->right;
40 }else{
41 cout<<"must be unique key"<<endl;
42 return ;
43 }
44 }
45 if(pre->value > node->value){
46 pre->left=node;
47 }else{
48 pre->right=node;
49 }
50 }
51
52 int BuildBTree(BTree *&T,int array[],int num){
53 assert(num>0);
54
55 T=new BTNode;
56 T->left=T->right=NULL;
57 T->value=array[0];
58
59 BTNode *tmp=NULL;
60
61 for(int i=1;i<num;i++){
62 tmp=new BTNode;
63 tmp->left=tmp->right=NULL;
64 tmp->value=array[i];
65 Insert(T,tmp);
66 //cout<<array[i]<<" * ";
67 }
68 cout<<endl;
69 //PrintTree(T);
70 return 1;
71 }
72
73 int BTreeToDoubleLinkList(BTree *&T,BTNode *&Head){
74 if(!T)return 0;
75
76
77 BTNode *pre,*next,*tmp,*connect;
78 pre=next=NULL;
79 Head=NULL;
80 //return 1;
81 stack<BTNode*> st;
82 st.push(T);
83 tmp=T;
84 int i=0;
86 while(!st.empty()){
87
88 tmp=st.top();
89 while(tmp->left){//一直向左边查找；
90 st.push(tmp->left);
91
92 tmp=tmp->left;
93 }
94
95 if(NULL == Head)Head=tmp;//记录头结点；
96 tmp=st.top();
97 st.pop();
98
99 if(NULL == pre){//记录前驱；
100 pre=tmp;
101 }else{
102 //进行链接；
103 pre->right=tmp;
104 tmp->left=pre;
105 pre=tmp;
106
107 }
108
109 if(tmp->right){
110 tmp=tmp->right;
111 st.push(tmp);
112 }else{
113 //当前元素出栈；
114 tmp=st.top();
115 st.pop();
116 while(!tmp->right){
117 //右节点为空，进行链接；
118 pre->right=tmp;
119 tmp->left=pre;//
120 pre=tmp;
121
122 if(st.empty())break;
123 tmp=st.top();
124 st.pop();
125
126 }
127
128 if(tmp->right){
129 //右节点不为空，进行链接，入栈；
130 pre->right=tmp;
131 tmp->left=pre;
132 pre=tmp;
133 st.push(tmp->right);
134 }
135
136
137 //tmp=tmp->right;
138 }
139 }
140 }
141
142
143 int main(){
144
145 //int array[]={10,6,11,4,9,13,8,12,16,7,15,14};
146 int array[]={14,13,15,7,16,10,20,9,12,19,18} ;
147 int num=sizeof(array)/sizeof(int);
148
149 BTree *T=NULL;
150 BTNode *Head=NULL;
151 BuildBTree(T,array,num);
152
153 BTreeToDoubleLinkList(T,Head);
154
155 BTNode *tmp=Head,*pre;
156
157 cout<<" \n in main print list"<<endl;
158
159 while(tmp){
160 cout<<tmp->value<<" ";
161 pre=tmp;
162 tmp=tmp->right;
163 }
164 cout<<" \nfrom tail to head"<<endl;
165 while(pre){
166 cout<<pre->value<<" ";
167 pre=pre->left;
168 }
169
170 cout<<endl;
171 DestoryLink(Head);
172
173 system("pause");
174 return 0;
175 }
176
177
178
179
180
181
182
183
184
185
186
187
188
189