构造二叉树，打印二叉树图形

  1 #include <iostream>
  2 #include <cmath>
  3 using namespace std;
  4 struct node
  5 {
  6     char c;
  7     int n;
  8     int level;
  9     struct node* lc;
 10     struct node* rc;
 11 };
 12 char pre[100];
 13 char in[100];
 14 char post[100];
 15 struct node* create_node()
 16 {
 17     struct node* p = new struct node;
 18     p->lc = p->rc = NULL;
 19     return p;
 20 }
 21 struct node* build_in_post(int s1, int e1, int s2, int e2)
 22 {
 23     struct node* p = create_node();
 24     for (int i = s1; i <= e1; i++)
 25     {
 26         if (post[e2] == in[i])
 27         {
 28             p->c = post[e2];
 29             if (i != s1)
 30             {
 31                 p->lc = build_in_post(s1, i - 1, s2, s2 + i - s1 - 1);
 32             }
 33             if (i != e1)
 34             {
 35                 p->rc = build_in_post(i + 1, e1, e2 - e1 + i, e2 - 1);
 36             }
 37             break;
 38         }
 39     }
 40     return p;
 41 }
 42 struct node* build_pre_in(int s1, int e1, int s2, int e2)
 43 {
 44     struct node* p = create_node();
 45     for (int i = s2; i <= e2; i++)
 46     {
 47         if (pre[s1] == in[i])
 48         {
 49             p->c = pre[s1];
 50             if (i != s2)
 51             {
 52                 p->lc = build_pre_in(s1 + 1, s1 + i - s2, s2, i - 1);
 53             }
 54             if (i != e2)
 55             {
 56                 p->rc = build_pre_in(s1 + i - s2 + 1, e1, i + 1, e2);
 57             }
 58             break;
 59         }
 60     }
 61     return p;
 62 }
 63 void pre_tra(struct node* t)
 64 {
 65     if (t)
 66     {
 67         cout << t->n << " ";
 68         if (t->lc)
 69             pre_tra(t->lc);
 70         if (t->rc)
 71             pre_tra(t->rc);
 72     }
 73 }
 74 void in_tra(struct node* t)
 75 {
 76     if (t)
 77     {
 78         if (t->lc)
 79             in_tra(t->lc);
 80         cout << t->n << " ";
 81         if (t->rc)
 82             in_tra(t->rc);
 83     }
 84 }
 85 void post_tra(struct node* t)
 86 {
 87     if (t)
 88     {
 89         if (t->lc)
 90             post_tra(t->lc);
 91         if (t->rc)
 92             post_tra(t->rc);
 93         cout << t->n <<" ";
 94     }
 95 }
 96 int get_h(struct node* t)
 97 {
 98     if (t)
 99     {
100         return get_h(t->lc) > get_h(t->rc) ? get_h(t->lc) + 1 : get_h(t->rc) + 1;
101     }
102     return 0;
103 }
104 int find_max(struct node* t)
105 {
106     if (t->rc)
107         return(find_max(t->rc));
108     else
109         return t->n;
110 }
111 int find_min(struct node* t)
112 {
113     if (t->lc)
114         return(find_min(t->lc));
115     else
116         return t->n;
117 }
118 void print_tree_int(struct node* t)
119 {
120     if (t)
121     {
122         struct node* q1[100];
123         int r1 = -1;
124         int f1 = -1;    
125         t->level = 1;
126         q1[++f1] = t;
127         int max_level = get_h(t);
128         while (r1 != f1)
129         {    
130             struct node* p = q1[++r1];
131             if (p->n == 0)
132             {
133                         if (p->level == max_level)break;
134                         q1[++f1] = create_node();
135                         q1[f1]->n = 0;
136                         q1[f1]->level = p->level + 1;
137                         q1[++f1] = create_node();
138                         q1[f1]->n = 0;
139                         q1[f1]->level = p->level + 1;
140             }
141             else
142             {
143                 if (p->level == max_level)break;
144                 if (p->lc)
145                 {
146                     p->lc->level = p->level + 1;
147                     q1[++f1] = p->lc;
148                 }
149                 else
150                 {
151                     struct node* pt = create_node();
152                     if (pt != NULL)
153                     {
154                         pt->n = 0;
155                         pt->level = p->level + 1;
156                         q1[++f1] = pt;
157                     }
158 
159                 }
160                 if (p->rc)
161                 {
162                     p->rc->level = p->level + 1;
163                     q1[++f1] = p->rc;
164                 }
165                 else
166                 {
167                     struct node* pt =create_node();
168                     if (pt != NULL)
169                     {
170                         pt->n = 0;
171                         pt->level = p->level + 1;
172                         q1[++f1] = pt;
173                     }
174                 }
175             }
176         }
177         int div = 1;
178         int width = 128;
179         int base[20];
180         base[0] = width;
181         r1 = -1;
182         base[max_level] = width / pow(2, max_level);
183         for (int i = max_level - 1; i >= 1; i--)
184         {
185             base[i] = base[i + 1] * 2;
186         }
187         int first[20] = { 0 };
188         for (int i = 1; i <= max_level; i++)
189         {
190             for (int j = i; j <= max_level; j++)
191             {
192                 first[i] += base[j]/2;
193             }
194         }
195         for (int i = 1; i <= max_level; i++)
196         {
197             int inc = base[i - 1];
198             if (i == 5)first[i] = 0;
199             for (int j = 0; j < first[i]; j++)
200             {
201                 cout << "-";
202             }
203             int cnt = 0;
204             while (r1 != f1 && q1[r1 + 1]->level == i)
205             {
206                 if (q1[r1 + 1]->n >= 10 && q1[r1 + 1]->n < 100)inc -= 1;
207                 else if (q1[r1 + 1]->n >= 1000 && q1[r1+1]->n < 10000)inc -= 2;
208                 else if (q1[r1 + 1]->n >= 10000)inc -= 3;
209                 if (i == 4 && cnt == 1)inc -= 1;
210                 if (i == 4 && cnt == 5)inc -= 2;
211                 if (i == 5 && cnt == 0)inc += 1;
212                 if (i == 5 && (cnt == 1 || cnt == 5 || cnt ==7  ||cnt == 13))inc -= 1;
213                 if (i == 5 && (cnt == 3)||(cnt == 10))inc -= 2;        
214                 if (i == 5 && cnt == 11)inc -= 3;
215                 cnt++;                
216                 cout << q1[++r1]->n;
217                 for (int k = 0; k < inc; k++)
218                 {
219                     cout << "-";
220                 }
221              inc = base[i - 1];
222             }
223             cout << endl;
224         }
225             cout << endl;
226     }
227 }
228 void print_tree_char(struct node* t)
229 {
230     if (t)
231     {
232         struct node* q1[100];
233         int r1 = -1;
234         int f1 = -1;
235         t->level = 1;
236         q1[++f1] = t;
237         int max_level = get_h(t);
238         while (r1 != f1)
239         {
240             struct node* p = q1[++r1];
241             if (p->n == 0)
242             {
243                 if (p->level == max_level)break;
244                 q1[++f1] = create_node();
245                 q1[f1]->c = '#';
246                 q1[f1]->level = p->level + 1;
247                 q1[++f1] = create_node();
248                 q1[f1]->c = '#';
249                 q1[f1]->level = p->level + 1;
250             }
251             else
252             {
253                 if (p->level == max_level)break;
254                 if (p->lc)
255                 {
256                     p->lc->level = p->level + 1;
257                     q1[++f1] = p->lc;
258                 }
259                 else
260                 {
261                     struct node* pt = create_node();
262                     if (pt != NULL)
263                     {
264                         pt->c = '#';
265                         pt->level = p->level + 1;
266                         q1[++f1] = pt;
267                     }
268 
269                 }
270                 if (p->rc)
271                 {
272                     p->rc->level = p->level + 1;
273                     q1[++f1] = p->rc;
274                 }
275                 else
276                 {
277                     struct node* pt = create_node();
278                     if (pt != NULL)
279                     {
280                         pt->c = '#';
281                         pt->level = p->level + 1;
282                         q1[++f1] = pt;
283                     }
284                 }
285             }
286         }
287         int div = 1;
288         int width = 128;
289         int base[20];
290         base[0] = width;
291         r1 = -1;
292         base[max_level] = width / pow(2, max_level);
293         for (int i = max_level - 1; i >= 1; i--)
294         {
295             base[i] = base[i + 1] * 2;
296         }
297         int first[20] = { 0 };
298         for (int i = 1; i <= max_level; i++)
299         {
300             for (int j = i; j <= max_level; j++)
301             {
302                 first[i] += base[j] / 2;
303             }
304         }
305         for (int i = 1; i <= max_level; i++)
306         {
307             int inc = base[i - 1];
308             if (i == 5)first[i] = 0;
309             for (int j = 0; j < first[i]; j++)
310             {
311                 cout << "-";
312             }
313             int cnt = 0;
314             while (r1 != f1 && q1[r1 + 1]->level == i)
315             {
316                 if (i == 4 && cnt == 1)inc -= 1;
317                 if (i == 4 && cnt == 5)inc -= 2;
318                 if (i == 5 && cnt == 0)inc += 1;
319                 if (i == 5 && (cnt == 1 || cnt == 5 || cnt == 7 || cnt == 13))inc -= 1;
320                 if (i == 5 && (cnt == 3) || (cnt == 10))inc -= 2;
321                 if (i == 5 && cnt == 11)inc -= 3;
322                 cnt++;
323                 cout << q1[++r1]->c;
324                 for (int k = 0; k < inc; k++)
325                 {
326                     cout << "-";
327                 }
328                 inc = base[i - 1];
329             }
330             cout << endl;
331         }
332         cout << endl;
333     }
334 }
335 void bracket_print_char(struct node* t)
336 {
337     if (t)
338     {
339         cout << t->c;
340         if (t->lc)
341         {                
342             cout << "(";
343             bracket_print_char(t->lc);        
344         }
345         if (t->rc)
346         {
347             if (!t->lc)
348             {
349                 cout << "(";
350             }
351             cout << ",";
352             bracket_print_char(t->rc);        
353         }
354         if(t->rc || t->lc)
355             cout << ")";
356     }
357     else
358     {
359         return;
360     }
361 }
362 void bracket_print_int(struct node* t)
363 {
364     if (t)
365     {
366         cout << t->n;
367         if (t->lc)
368         {
369             cout << "(";
370             bracket_print_int(t->lc);
371         }
372         if (t->rc)
373         {
374             if (!t->lc)
375             {
376                 cout << "(";
377             }
378             cout << ",";
379             bracket_print_int(t->rc);
380         }
381         if (t->rc || t->lc)
382             cout << ")";
383     }
384     else
385     {
386         return;
387     }
388 }
389 struct node* insert(struct node* head, int num)
390 {
391     if (!head)
392     {
393         head = create_node();
394         head->n = num;
395     }
396     else
397     {
398         if (num <= head->n)
399         {
400             head->lc = insert(head->lc, num);
401         }
402         else if (num > head->n)
403         {
404             head->rc = insert(head->rc, num);
405         }
406     }
407     return head;
408 }
409 int main()
410 {
411     cout <<endl<< "-----------------------根据给出的一组数据构造二叉树-------------------------" << endl;
412     cout << "数字个数：";
413     int n1;
414     cin >> n1;
415     int num[100];
416     for (int i = 0; i < n1; i++)
417     {
418         cin >> num[i];
419     }
420     struct node* head2 = NULL;
421     for (int i = 0; i < n1; i++)
422     {
423         head2 = insert(head2, num[i]);
424     }
425     cout << "前序遍历：";
426     pre_tra(head2);
427     cout << endl;
428     cout << "中序遍历：";
429     in_tra(head2);
430     cout << endl;
431     cout << "后序遍历：";
432     post_tra(head2);
433     cout << endl;
434     cout << "深度：" << get_h(head2) << endl;
435     cout << "最大值：" << find_max(head2) << endl;
436     cout << "最小值：" << find_min(head2) << endl;
437     cout << "嵌套括号表示：";
438     bracket_print_int(head2);
439     cout << endl;
440     cout << "根据输入数据构造：" << endl;
441     if (get_h(head2) <= 5)
442     {
443         cout << "图形：（0表示没有结点）" << endl;
444         print_tree_int(head2);
445     }
446     else
447     {
448         cout << "深度大于5，无法输出" << endl;
449     }
450     cout << "-----------------------根据前中序，中后序构造二叉树-------------------------" <<endl << endl;
451     cout << "前序："; cin >> pre;
452     cout << "中序："; cin >> in;
453     cout << "后序："; cin >> post;
454     int n = strlen(pre);
455     struct node* head = build_pre_in(0, n - 1, 0, n - 1);
456     struct node* head1 = build_in_post(0, n - 1, 0, n - 1);
457     int h1 = get_h(head);
458     int h2 = get_h(head1);
459 
460     cout << "根据前中序构造：" << endl;
461     cout << "嵌套括号表示：";
462     bracket_print_char(head);    
463     cout << endl;
464     cout << "深度：" << h2 << endl;
465     if (h1 <= 5)
466     {
467         cout << "图形：（'#'表示没有结点）" << endl;
468         print_tree_char(head);
469     }
470     else
471     {
472         cout << "深度大于5，无法打印图形" << endl;
473     }
474     cout << endl;
475     cout << "根据中后序构造：" << endl;
476     cout << "嵌套括号表示：";
477     bracket_print_char(head1);
478     cout << endl;    
479     cout << "深度：" << h2 << endl;
480     if (h1 <= 5)
481     {
482         cout << "图形：（'#'表示没有结点）" << endl;
483         print_tree_char(head1);
484     }
485     else
486     {
487         cout << "深度大于5，无法打印图形" << endl;
488     }
489     return 0;
490 }

测试用例：

8

12 33 234 1 44 32 11 9

ABCDEF

CBDAEF

CDBFEA

结果：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/2020R/p/12968672.html