二叉树的遍历（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-&gt;front-&gt;next = NULL;
  pQ-&gt;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,