二叉树的遍历（C语言，层序）
实现下面图中的二叉树层序遍历#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
# 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,
文档来源：51CTO技术博客https://blog.51cto.com/sndapk/3123569
页:
[1]