实现下面图中的二叉树层序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <unistd.h>typedef struct node { char data; struct node *lchild; struct node *rchild;}NODE, *PNODE;typedef struct qnode { PNODE pnode; struct qnode *next;}QNODE, *PQNODE;typedef struct queue { PQNODE front; PQNODE rear; int size;}QUEUE, *PQUEUE;PNODE CreateTree(void);void initQueue(PQUEUE);void enQueue(PQUEUE, PNODE);bool deQueue(PQUEUE, PNODE *);void levelTraversal(PNODE);PNODE CreateTree(void){ PNODE pA = (PNODE)malloc(sizeof(NODE)); PNODE pB = (PNODE)malloc(sizeof(NODE)); PNODE pC = (PNODE)malloc(sizeof(NODE)); PNODE pD = (PNODE)malloc(sizeof(NODE)); PNODE pE = (PNODE)malloc(sizeof(NODE)); PNODE pF = (PNODE)malloc(sizeof(NODE)); PNODE pG = (PNODE)malloc(sizeof(NODE)); pA->data = 'A'; pB->data = 'B'; pC->data = 'C'; pD->data = 'D'; pE->data = 'E'; pA->lchild = pB; pA->rchild = pC; pB->lchild = pB->rchild = NULL; pC->lchild = pD; pC->rchild = NULL; pD->lchild = NULL; pD->rchild = pE; pE->lchild = pE->rchild = NULL; return pA;}void initQueue(PQUEUE pQ) { pQ->front = pQ->rear = (PQNODE)malloc(sizeof(QNODE)); if (! pQ->front) { printf("init malloc error!\n"); exit(-1); } pQ->front->next = NULL; pQ->size = 0;}void enQueue(PQUEUE pQ, PNODE pnode) { //printf("en_queue %c ", pnode->data); PQNODE pNew; pNew = (PQNODE)malloc(sizeof(QNODE)); if (!pNew) { printf(" en_queue malloc error!\n"); exit(-1); } pNew->pnode = pnode; pNew->next = NULL; pQ->rear->next = pNew; pQ->rear = pNew; pQ->size++; //printf(" success.\n");}bool deQueue(PQUEUE pQ, PNODE *ppnode) { //printf("de_queue..."); PQNODE tmp; if (pQ->front->next == NULL) { printf(" failed, queue empty!\n"); return false; } tmp = pQ->front->next; *ppnode = tmp->pnode; pQ->front->next = tmp->next; // 最后一个节点出队特殊处理 if (tmp->next == NULL) pQ->rear = pQ->front; free(tmp); pQ->size--; //printf("success, value: %c\n", (*ppnode)->data); return true;}void levelTraversal(PNODE pnode){ if (pnode) { QUEUE Q; PNODE tmp; initQueue(&Q); enQueue(&Q, pnode); int levelSize, level; level = 0; while (Q.size) { sleep(1); level++; levelSize = Q.size; printf("traversal level %d have %d nodes:", level, levelSize); for (int i=0; i<levelSize; i++) { deQueue(&Q, &tmp); printf(" %c,", tmp->data); if (tmp->lchild) enQueue(&Q, tmp->lchild); if (tmp->rchild) enQueue(&Q, tmp->rchild); } printf("\n"); } }}int main(void){ PNODE T = CreateTree(); printf("层序遍历结果:\n"); levelTraversal(T); return 0;} |
output
[root@8be225462e66 c]# gcc level_traversal.c && ./a.out
层序遍历结果:
traversal level 1 have 1 nodes: A,
traversal level 2 have 2 nodes: B, C,
traversal level 3 have 1 nodes: D,
traversal level 4 have 1 nodes: E,
到此这篇关于C语言二叉树层序遍历的文章就介绍到这了,更多相关C语言遍历内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.51cto.com/sndapk/3123569
