学习二叉树时，如果能直观显示，测试程序的时候会方便许多。
实现树形打印的标准方法是利用队列，此处参考的是CSDN上的一篇文章：树状显示二叉树， 原程序使用C++实现，这里使用C。
算法中使用了两个队列，一个用于存储树的结点，另一个用于存储打印过程中每个结点对应的信息。
上一篇文章写了可以利用 void 指针来实现模板，这一次嫌麻烦没有用这个方法，复制粘贴了两个队列。
改天试一试能不能把 void 指针的赋值抽象成一套函数来用用。
如同上面那篇文章中介绍的，此打印程序的核心思想是利用父结点的坐标 pos, 和每一层的偏移量 offset 计算左右子结点的位置。
左结点的坐标是 pos - offset, 右结点的坐标是 pos + offset.
实现代码如下：
1 // content of "BST.h"
2 #include<stdio.h>
3 #include<stdlib.h>
4
5 // definition of the Tree.
6
7 struct Node {
8 int key;
9 struct Node *LeftChild;
10 struct Node *RightChild;
11 };
12
13 typedef struct Node *Position;
14 typedef struct Node *SearchTree;
15
16 int GetHeight(SearchTree T);
17 SearchTree Insert(SearchTree T, int data);
18 Position Find(SearchTree T, int data);
19 SearchTree Delete(SearchTree T, int data);
20 Position FindMin(SearchTree T);
21
22 void Error1(char *s);
23
24 // Definition of the Queue of Nodes.
25
26 typedef Position ElementType;
27
28 struct Q_Item {
29 ElementType data;
30 struct Q_Item *next;
31 };
32
33 typedef struct Q_Item *PtrToItem;
34
35 struct Qrec {
36 PtrToItem front, end;
37 };
38
39 typedef struct Qrec *Queue;
40
41 Queue CreateQ(void);
42 void InQ(Queue Q, ElementType data);
43 ElementType OutQ(Queue Q);
44 void Clear(Queue Q);
45 int IsEmpty(Queue Q);
46 int Power(int x, int n);
47
48 // Definition of the Queue of the info needed in PrintDepth.
49
50 struct infoNode {
51 int pos;
52 int space;
53 int level;
54 int newline;
55 struct infoNode *next;
56 };
57
58 typedef struct infoNode *infoItem;
59
60 struct infoQrec {
61 infoItem front, end;
62 };
63
64 typedef struct infoQrec *infoQ;
65
66 infoItem MakeItem(int pos, int space, int level, int newline);
67 infoQ CreateInfoQ(void);
68 void Pushback(infoQ Q, infoItem item);
69 infoItem PopFront(infoQ Q);
70 int InfoQEmpty(infoQ Q);
71
72 // the final function is here
73 75 void PrintDepth_2(SearchTree T); 1 #include"BST.h"
2 #define TRUE 1
3 #define FALSE 0
4
5 // the Queue of TreeNodes.
6
7 Queue CreateQ(void)
8 {
9 Queue Q = (Queue)malloc(sizeof(struct Qrec));
10 if(!Q)
11 Error1("out of space for Queue for TreeNode");
12
13 Q->front = Q->end = NULL;
14
15 return Q;
16 }
17
18 void InQ(Queue Q, ElementType data)
19 {
20 PtrToItem newNode = (PtrToItem)malloc(sizeof(ElementType));
21 if(!newNode)
22 {
23 printf("no space for newNode\n");
24 exit(1);
25 }
26
27 newNode->data = data;
28 newNode->next = NULL;
29
30 if(!Q->end)
31 Q->front = Q->end = newNode;
32 else
33 {
34 Q->end->next = newNode;
35 Q->end = newNode;
36 }
37 }
38
39 ElementType OutQ(Queue Q)
40 {
41 ElementType data;
42 PtrToItem temp;
43
44 if(!Q->front)
45 {
46 printf("the Queue is empty\n");
47 exit(1);
48 }
49
50 temp = Q->front;
51 data = temp->data;
52
53 if(temp->next == NULL)
54 Q->front = Q->end = NULL;
55 else
56 Q->front = temp->next;
57
58 free(temp);
59
60 return data;
61 }
62
63 void Clear(Queue Q)
64 {
65 PtrToItem curr, temp;
66
67 curr = Q->front;
68
69 while(curr)
70 {
71 temp = curr;
72 curr = curr->next;
73 free(temp);
74 }
75
76 free(Q);
77
78 }
79
80 int IsEmpty(Queue Q)
81 {
82 return Q->front == NULL;
83 }
84
85 int Power(int x, int n)
86 {
87 if(n == 0)
88 return 1;
89 else if( n % 2 )
90 return Power(x*x, n/2) * x;
91 else
92 return Power(x*x, n/2);
93 }
94
95 // the Queue for printing information.
96
97 infoItem MakeItem(int pos, int space, int level, int newline)
98 {
99 infoItem newItem = (infoItem)malloc(sizeof(struct infoNode));
100 if(!newItem)
101 Error1("out of space for infoNode");
102
103 newItem->pos = pos;
104 newItem->space = space;
105 newItem->level = level;
106 newItem->newline = newline;
107 newItem->next = NULL;
108
109 return newItem;
110 }
111
112 infoQ CreateInfoQ(void)
113 {
114 infoQ Q = (infoQ)malloc(sizeof(struct infoQrec));
115 if(!Q)
116 Error1("out of space for infoQ");
117
118 Q->front = Q->end = NULL;
119
120 return Q;
121 }
122
123 void Pushback(infoQ Q, infoItem item)
124 {
125 infoItem newItem = item;
126
127 if(!Q->end)
128 Q->front = Q->end = newItem;
129 else
130 {
131 Q->end->next = newItem;
132 Q->end = newItem;
133 }
134 }
135
136 infoItem PopFront(infoQ Q)
137 {
138 infoItem item;
139
140 if(!Q->front)
141 Error1("the Queue is empty");
142
143 item = Q->front;
144
145 if(item->next == NULL)
146 Q->front = Q->end = NULL;
147 else
148 Q->front = item->next;
149
150 return item;
151 }
152
153 void ClearInfoQ(infoQ Q)
154 {
155 infoItem curr, temp;
156
157 curr = Q->front;
158
159 while(curr)
160 {
161 temp = curr;
162 curr = curr->next;
163 free(temp);
164 }
165
166 free(Q);
167
168 }
169
170 int InfoQEmpty(infoQ Q)
171 {
172 return Q->front == NULL;
173 }
174
175
176
177 // this function also print the NULL nodes,
178 // so the tree will look better and prettier,
179 // but also acquire a larger screen because
180 // this function divides the screen into
181 // many blocks, so the space here is consuming.
182 //
183 // | | | |44| | | |
184 // | |29| | | |66| |
185 // |11| |33| |54| |77|
186 //
187 // the key idea of this program is:
188 // while the node is not at the bottom,
189 // no matter if there is a node in the tree,
190 // we create a infoItem with the printing information,
191 // and push a NULL into the Queue.
192 // when we pop the elements out of the Queue,
193 // if the Node it contains is a NULL, we print some
194 // blank block, otherwise we print the key in the Node.
195
196
197 void PrintDepth(SearchTree T)
198 {
199 Position currNode;
200 Queue Q = CreateQ();
201 infoQ IQ = CreateInfoQ();
202 infoItem newInfo, currInfo, preInfo;
203 int height = GetHeight(T);
204 int ScreenWidth = Power(2, height+1);
205 int pos, level, space, newline;
206 int dataWidth = 1; // dataWidth is the width of the block.
207 int i;
208
209 InQ(Q, T);
210 level = 1;
211 pos = ScreenWidth >> level;
212 space = pos;
213 newline = TRUE;
214
215 newInfo = MakeItem(pos, space, level, newline);
216 Pushback(IQ, newInfo);
217
218 preInfo = newInfo;
219
220 while(!IsEmpty(Q))
221 {
222 currNode = OutQ(Q);
223 currInfo = PopFront(IQ);
224
225 if(currInfo->newline)
226 printf("\n");
227
228 for(i=0; i<currInfo->space; i++)
229 printf(" ");
230
231 if(currNode)
232 printf("%d",currNode->key);
233 else
234 printf(" ");
235
236 if(currInfo->level < height+1) // if the node is not at the bottom,
237 { // always create 2 child nodes.
238 level = currInfo->level + 1;
239 pos = currInfo->pos - (ScreenWidth >> level); // the left child.
240 if(level > preInfo->level)
241 {
242 newline = TRUE;
243 space = pos;
244 }
245 else
246 {
247 newline = FALSE;
248 space = pos - preInfo->pos;
249 }
250
251 space--; // set aside space for the data to be printed.
252 newInfo = MakeItem(pos, space, level, newline);
253
254 Pushback(IQ, newInfo);
255
256 preInfo = newInfo;
257
258 if(currNode) // if there is a node in a tree, create the left child.
259 {
260 if(currNode->LeftChild)
261 InQ(Q, currNode->LeftChild);
262 else
263 InQ(Q, NULL);
264 }
265 else // if there is a NULL, create the "left child" for NULL.
266 InQ(Q, NULL);
267
268 pos = currInfo->pos + (ScreenWidth >> level); // the right child.
269 newline = FALSE;
270 space = pos - preInfo->pos;
271 space--;
272
273 newInfo = MakeItem(pos, space, level, newline);
274
275 Pushback(IQ, newInfo);
276
277 if(currNode)
278 {
279 if(currNode->RightChild)
280 InQ(Q, currNode->RightChild);
281 else
282 InQ(Q, NULL);
283 }
284 else
285 InQ(Q, NULL);
286
287 preInfo = newInfo;
288
289 }
290
291 }
292
293 printf("\n\n");
294 } 转载于:https://www.cnblogs.com/jeffo/p/print_binary_tree.html
![终端环境之tmux[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)