二叉树的遍历：层序，先序，中序，后序(C语言)

大家好，欢迎来到IT知识分享网。

1.层序遍历

#pragma once #include "BinaryTree.h"//引入二叉树的头文件 typedef BTNode* QDataType;//队列节点的类型为二叉树节点 typedef struct QueueNode { 
    QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { 
    QNode* head; QNode* tail; int size; }Queue; //队列的初始化 void QueueInit(Queue* pq); //队列的销毁 void QueueDeatroy(Queue* q); //队列的输入 void QueuePush(Queue* pq, QDataType x); //队列的删除 void QueuePop(Queue* pq); //队列头结点的值 QDataType QueueFront(Queue* pq); //队列尾结点的值 QDataType QueueBack(Queue* pq); //队列是空 bool QueueEmpty(Queue* pq); //队列的大小 int QueueSize(Queue* pq); 

Queue.c中的代码：

#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" void QueueInit(Queue* pq) { 
    pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QueueDeatroy(Queue* pq) { 
    assert(pq); QNode* cur = pq->head; while (cur) { 
    QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { 
    assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { 
    perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { 
    pq->head = pq->tail = newnode; } else { 
    pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { 
    free(pq->head); pq->head = pq->tail = NULL; } else { 
    QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } QDataType QueueFront(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { 
    assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { 
    assert(pq); return pq->head == NULL && pq->tail == NULL; } 

#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef struct BinaryTreeNode { 
    int val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyBTNode(int a); // 二叉树先序遍历  void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); 

二叉树BinaryTreeNode.c代码：

#define _CRT_SECURE_NO_WARNINGS 1 #include "BinaryTree.h" #include "Queue.h" //构造二叉树的结点 BTNode* BuyBTNode(int a) { 
    BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { 
    return; } root->val = a; root->left = NULL; root->right = NULL; return root; } // 二叉树先序遍历 void BinaryTreePrevOrder(BTNode* root) { 
    if (root == NULL) return; printf("%d ", root->val); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { 
    if (root == NULL) return; BinaryTreeInOrder(root->left); printf("%d ", root->val); BinaryTreeInOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { 
    if (root == NULL) return; BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%d ", root->val); } //层序遍历 void BinaryTreeLevelOrder(BTNode* root) { 
    Queue q; QueueInit(&q); if (root) { 
    QueuePush(&q, root); } while (!QueueEmpty(&q)) { 
    BTNode* front = QueueFront(&q); printf("%d ", front->val); QueuePop(&q); if (front->left) { 
    QueuePush(&q, front->left); } if (front->right) { 
    QueuePush(&q, front->right); } } QueueDeatroy(&q); } 

将以上代码放到一个文件中：

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h>// 断言 typedef struct BinaryTreeNode { 
    int val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyBTNode(int a); // 二叉树先序遍历  void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); typedef BTNode* QDataType;//队列节点的类型为二叉树节点 typedef struct QueueNode { 
    QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { 
    QNode* head; QNode* tail; int size; }Queue; //队列的初始化 void QueueInit(Queue* pq); //队列的销毁 void QueueDeatroy(Queue* q); //队列的输入 void QueuePush(Queue* pq, QDataType x); //队列的删除 void QueuePop(Queue* pq); //队列头结点的值 QDataType QueueFront(Queue* pq); //队列尾结点的值 QDataType QueueBack(Queue* pq); //队列是空 bool QueueEmpty(Queue* pq); //队列的大小 int QueueSize(Queue* pq); void QueueInit(Queue* pq) { 
    pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QueueDeatroy(Queue* pq) { 
    assert(pq); QNode* cur = pq->head; while (cur) { 
    QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { 
    assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { 
    perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { 
    pq->head = pq->tail = newnode; } else { 
    pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { 
    free(pq->head); pq->head = pq->tail = NULL; } else { 
    QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } QDataType QueueFront(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { 
    assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { 
    assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { 
    assert(pq); return pq->head == NULL && pq->tail == NULL; } //构造二叉树的结点 BTNode* BuyBTNode(int a) { 
    BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { 
    return; } root->val = a; root->left = NULL; root->right = NULL; return root; } // 二叉树先序遍历 void BinaryTreePrevOrder(BTNode* root) { 
    if (root == NULL) return; printf("%d ", root->val); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { 
    if (root == NULL) return; BinaryTreeInOrder(root->left); printf("%d ", root->val); BinaryTreeInOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { 
    if (root == NULL) return; BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%d ", root->val); } //层序遍历 void BinaryTreeLevelOrder(BTNode* root) { 
    Queue q; QueueInit(&q); if (root) { 
    QueuePush(&q, root); } while (!QueueEmpty(&q)) { 
    BTNode* front = QueueFront(&q); printf("%d ", front->val); QueuePop(&q); if (front->left) { 
    QueuePush(&q, front->left); } if (front->right) { 
    QueuePush(&q, front->right); } } QueueDeatroy(&q); } int main() { 
    //构建一个如上图所示的二叉树 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); BTNode* n7 = BuyBTNode(7); BTNode* n8 = BuyBTNode(8); n1->left = n2; n1->right = n3; n2->left = n4; n3->left = n5; n3->right = n6; n4->right = n7; n6->left = n8; printf("层序遍历:"); BinaryTreeLevelOrder(n1); printf("\n"); printf("先序遍历:"); BinaryTreePrevOrder(n1); printf("\n"); printf("中序遍历:"); BinaryTreeInOrder(n1); printf("\n"); printf("后序遍历:"); BinaryTreePostOrder(n1); printf("\n"); return 0; } 

打印结果如下：