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

[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语言遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！