二叉树方面的问题

  1   1 #include <iostream>
  2   2 #include <stdio.h>
  3   3 #include <string>
  4   4 #include <string.h>
  5   5 #include <algorithm>
  6   6 #include <vector>
  7   7 #include <map>
  8   8 #include <stack>
  9   9 #define maxn 110
 10  10 #define inf 0x7fffffff
 11  11 using namespace std;
 12  12 int num, pos;
 13  13 struct BTNode
 14  14 {
 15  15     int data;
 16  16     BTNode* lchild;
 17  17     BTNode* rchild;
 18  18 };
 19  19 // 二叉排序树插入节点
 20  20 void InsertBTNode(BTNode*& root, int k)
 21  21 {
 22  22     if(NULL == root)
 23  23     {
 24  24         root = (BTNode*)malloc(sizeof(BTNode));
 25  25         root->data = k;
 26  26         root->lchild = NULL;
 27  27         root->rchild = NULL;
 28  28     }
 29  29     else
 30  30     {
 31  31         if(k < root->data)InsertBTNode(root->lchild, k);
 32  32         else InsertBTNode(root->rchild, k);
 33  33     }
 34  34 }
 35  35 // 递归先序遍历
 36  36 void PreOrderTraverse(BTNode* root)
 37  37 {
 38  38     if(NULL != root)
 39  39     {
 40  40         printf("%d ", root->data);
 41  41         PreOrderTraverse(root->lchild);
 42  42         PreOrderTraverse(root->rchild);
 43  43     }
 44  44 
 45  45 }
 46  46 // 递归中序遍历
 47  47 void MidOrderTraverse(BTNode* root)
 48  48 {
 49  49     if(NULL != root)
 50  50     {
 51  51         MidOrderTraverse(root->lchild);
 52  52         printf("%d ", root->data);
 53  53         MidOrderTraverse(root->rchild);
 54  54     }
 55  55 }
 56  56 // 递归后续遍历
 57  57 void LastOrderTraverse(BTNode* root)
 58  58 {
 59  59     if(NULL != root)
 60  60     {
 61  61         LastOrderTraverse(root->lchild);
 62  62         LastOrderTraverse(root->rchild);
 63  63         printf("%d ", root->data);
 64  64     }
 65  65 }
 66  66 
 67  67 struct StackNode
 68  68 {
 69  69     BTNode* pBTNode;
 70  70     bool left;
 71  71     bool right;
 72  72     StackNode(){}
 73  73     StackNode(BTNode* x, bool y, bool z)
 74  74     {
 75  75         pBTNode = x;
 76  76         left = y;
 77  77         right = z;
 78  78     }
 79  79 };
 80  80 /*
 81  81 非递归遍历，对于任意一个节点（叶子节点也一样）都有左右两边是否访问过的属性，
 82  82 根据左右边是否被访问过，按照顺序实现前中后序的遍历，然后在判断是否有左右孩子，
 83  83 ,如，非递归先序遍历， 节点在入站前， 先输出，然后看左边是否访问过，没有的话，在看
 84  84 是否有左孩子，有左孩子的话，就输出左孩子的值，把左孩子加入栈中(左孩子的左右两边是没有被访问过的)；
 85  85 ，当发现左边被访问过了，再看右边是否访问过，没有的话，是否有右孩子....；若左右都访问过了，则出栈。
 86  86 */
 87  87 // 非递归先序
 88  88 void Pre_NoRecurTraverse(BTNode* root)
 89  89 {
 90  90     if(NULL ==  root)return ;
 91  91     stack<StackNode>my_stack;
 92  92     printf("%d ", root->data);
 93  93     my_stack.push(StackNode(root, true, true));
 94  94     while(!my_stack.empty())
 95  95     {
 96  96         StackNode p = my_stack.top();
 97  97         if(true == p.left)
 98  98         {
 99  99             p.left = false;
100 100             my_stack.pop();
101 101             my_stack.push(p);
102 102             if(NULL != p.pBTNode->lchild)
103 103             {
104 104                 printf("%d ", p.pBTNode->lchild->data);
105 105                 my_stack.push(StackNode(p.pBTNode->lchild, true, true));
106 106             }
107 107         }
108 108         else
109 109         {
110 110             if(true == p.right)
111 111             {
112 112                 p.right = false;
113 113                 my_stack.pop();
114 114                 my_stack.push(p);
115 115                 if(NULL != p.pBTNode->rchild)
116 116                 {
117 117                     printf("%d ", p.pBTNode->rchild->data);
118 118                     my_stack.push(StackNode(p.pBTNode->rchild, true, true));
119 119                 }
120 120             }
121 121             else
122 122                 my_stack.pop();
123 123         }
124 124     }
125 125 }
126 126 // 非递归中序
127 127 void Mid_NoRecurTraverse(BTNode* root)
128 128 {
129 129     if(NULL == root)return ;
130 130     stack<StackNode>my_stack;
131 131     my_stack.push(StackNode(root, true, true));
132 132     while(!my_stack.empty())
133 133     {
134 134         StackNode p = my_stack.top();
135 135         if(true == p.left)
136 136         {
137 137             p.left = false;
138 138             my_stack.pop();
139 139             my_stack.push(p);
140 140             if(NULL != p.pBTNode->lchild)
141 141             {
142 142                 my_stack.push(StackNode(p.pBTNode->lchild, true,true));
143 143             }
144 144         }
145 145         else
146 146         {
147 147             if(true == p.right)
148 148             {
149 149                 printf("%d ", p.pBTNode->data);
150 150                 p.right = false;
151 151                 my_stack.pop();
152 152                 my_stack.push(p);
153 153                 if(NULL != p.pBTNode->rchild)
154 154                 {
155 155                     my_stack.push(StackNode(p.pBTNode->rchild, true, true));
156 156                 }
157 157             }
158 158             else
159 159                 my_stack.pop();
160 160         }
161 161 
162 162     }
163 163 }
164 164 // 非递归后序
165 165 void Last_NoRecurTraverse(BTNode* root)
166 166 {
167 167     if(NULL ==  root)return;
168 168     stack<StackNode>my_stack;
169 169     my_stack.push(StackNode(root, true, true));
170 170     while(!my_stack.empty())
171 171     {
172 172         StackNode p = my_stack.top();
173 173         if(true == p.left)
174 174         {
175 175             p.left = false;
176 176             my_stack.pop();
177 177             my_stack.push(p);
178 178             if(NULL!=p.pBTNode->lchild)
179 179                 my_stack.push(StackNode(p.pBTNode->lchild, true, true));
180 180 
181 181         }
182 182         else
183 183         {
184 184             if(true == p.right)
185 185             {
186 186                 p.right = false;
187 187                 my_stack.pop();
188 188                 my_stack.push(p);
189 189                 if(NULL != p.pBTNode->rchild)
190 190                     my_stack.push(StackNode(p.pBTNode->rchild, true, true));
191 191             }
192 192             else
193 193             {
194 194                 printf("%d ", p.pBTNode->data);
195 195                 my_stack.pop();
196 196             }
197 197         }
198 198     }
199 199 }
200 200 // 根据先序和中序建树
201 201 BTNode* ConsrtcutTree(int pre[], int preL, int preR, int mid[], int midL, int midR)
202 202 {
203 203     BTNode* root = (BTNode*)malloc(sizeof(BTNode));
204 204     root->data = pre[preL];
205 205     root->lchild = root->rchild = NULL;
206 206     if(preL == preR)return root;
207 207     int k = pre[preL];
208 208     int num = 0;
209 209     int pos = midL;
210 210     while(mid[pos]!=k)
211 211     {
212 212         num++;
213 213         pos++;
214 214     }
215 215     if(pos > midL)root->lchild = ConsrtcutTree(pre, preL+1, preL+num, mid, midL, pos - 1);
216 216     if(pos < midR)root->rchild = ConsrtcutTree(pre, preL+num+1, preR, mid, pos+1, midR);
217 217 
218 218     return root;
219 219 
220 220 }
221 221 int main()
222 264 {
223 265     /*数据
224 
225             7
226             7 4 9 5 9 6 8
227             7
228             7 4 5 6 9 9 8
229             4 5 6 7 8 9 9
230 
231  
232 
233 
234 　　     */
235 266     //freopen("data.txt", "r", stdin);
236 267     BTNode* root = NULL;
237 268     int n,a;
238 269     scanf("%d", &n);
239 270     for(int i = 0; i < n;++i)
240 271     {
241 272         scanf("%d", &a);
242 273         InsertBTNode(root, a);
243 274     }
244 275     printf("
先序遍历：
");
245 276     PreOrderTraverse(root);
246 277     printf("
中序遍历：
");
247 278     MidOrderTraverse(root);
248 279     printf("
后序遍历：
");
249 280     LastOrderTraverse(root);
250 281     printf("
非递归先序遍历:
");
251 282     Pre_NoRecurTraverse(root);
252 283 
253 284     printf("
非递归中序遍历:
");
254 285     Mid_NoRecurTraverse(root);
255 286 
256 287     printf("
非递归后序遍历:
");
257 288     Last_NoRecurTraverse(root);
258 289 
259 290 
260 291     printf("根据先序和中序建树：
");
261 292     scanf("%d", &n);
262 293     printf("输入先序：
");
263 294     int pre[maxn];
264 295     int mid[maxn];
265 296     for(int i = 0 ; i < n;++i)
266 297         scanf("%d", &pre[i]);
267 298     printf("输入中序：
");
268 299     for(int i = 0 ; i < n;++i)
269 300         scanf("%d", &mid[i]);
270 301     BTNode* head = NULL;
271 302     head = ConsrtcutTree(pre, 0, n-1, mid, 0, n-1);
272 303 
273 304     printf("
先序遍历：
");
274 305     PreOrderTraverse(head);
275 306 
276 307     printf("
将树序列化树:
");
277 308     char str[maxn];
278 309     num = 0;
279 310     PreLinearTree(root, str);
280 311 
281 312     printf("
将序列化变为树:
");
282 313     BTNode* p = NULL;
283 314     pos = 0;
284 315     p = ReverseLinearTree(str);
285 316     printf("
先序遍历：
");
286 317     PreOrderTraverse(p);
287 318 
288 319 
289 320 
290 321 
291 322 }

View Code

序列化的意思是将内存中的一些特定的结构，变成有格式信息的字符串。如，对于链表而言，我们可以将1->2->3->NULL这样的链表序列化为"1,2,3"。对于序列化算法，必须支持反序列化，及在约定的格式下，可以将满足格式要求的字符串重新构造为想要的结构。

我们采用的是先序遍历实现序列话，为什么采用先序遍历，因为先序的话，是先找到的根，而中序和后序不是，这样反序列话时机不方便

为了能够在重构二叉树时结点能够插入到正确的位置，在使用先序遍历保存二叉树到文件中的时候需要把NULL结点也保存起来（可以使用特殊符号如“#”来标识NULL结点）。

假定二叉树如下所示：

    _30_
   /       
  10    20
 /     /  
50    45  35

则使用先序遍历，保存到文件中的内容如下：

30 10 50 # # # 20 45 # # 35 # #

序列化代码：

 1 void PreLinearTree(BTNode* root, char str[])
 2 {
 3     if(NULL == root)
 4     {
 5         printf("# ");
 6         str[num++] = '#';
 7         return;
 8     }
 9     else
10     {
11         printf("%d ", root->data);
12         str[num++] = '0' + root->data;
13         PreLinearTree(root->lchild, str);
14         PreLinearTree(root->rchild, str);
15     }
16 
17 }

View Code

反序列化：

用先序遍历的思想每次读取一个结点，如果读取到NULL结点的标识符号“#”，则忽略它。如果读取到结点数值，则插入到当前结点，然后遍历左孩子和右孩子。

 1 BTNode* ReverseLinearTree(char str[])
 2 {
 3     if('#' == str[pos])
 4     {
 5         ++pos;// 这个地方容易忘
 6         return NULL;
 7     }
 8     else
 9     {
10         BTNode* root = NULL;
11         root  = (BTNode* )malloc(sizeof(BTNode));
12         root->data = str[pos] - '0';
13         ++pos;
14         root->lchild = ReverseLinearTree(str);
15         root->rchild = ReverseLinearTree(str);
16         return root;
17     }
18     
19 }

View Code

当然也可以采用层次遍历的方法来实现序列化，原理是和上面一样的