前言
二叉树的遍历有：
前序/中序/后序的递归结构遍历以及层序遍历。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
前序遍历（Preorder Traversal）
深度优先搜索（DFS)通常指的就是前序遍历（也叫先序遍历）；
遍历顺序：当前结点（根节点 ）, 左子树, 右子树 即访问根结点的操作发生在遍历其左右子树之前
代码实现：
typedef struct BTNode { char _data; struct BTNode* _left; struct BTNode* _right; }BTNode; // 二叉树前序遍历 void Preorder(BTNode* root) { if (root == NULL) //如果为空，直接返回 后两个遍历简化此过程 return; printf("%d", root->_data); Preorder(root->_left); Preorder(root->_right); }
图解：
中序遍历历(Inorder Traversal)
遍历顺序：左子树，根节点，右子树 访问根结点的操作发生在遍历其左右子树之中（间）。
代码实现：
typedef struct BTNode { char _data; struct BTNode* _left; struct BTNode* _right; }BTNode; //二叉树中序遍历 void Inorder(BTNode* root) { if(root) { Inorder(root->_left); printf("%c ", root->_data); Inorder(root->_right); } }
后序遍历(Postorder Traversal)
遍历顺序：左子树，右子树，根节点 访问根结点的操作发生在遍历其左右子树之后。
代码实现：
typedef struct BTNode { char _data; struct BTNode* _left; struct BTNode* _right; }BTNode; // 二叉树后序遍历 void PostOrder(BTNode* root) { if (root) { PostOrder(root->_left); PostOrder(root->_right); printf("%c", root->_data); } }
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为
根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
层序遍历
也叫广度优先搜索(BFS）。遍历顺序：从所在二叉树的根节点出发，从上到下按层遍历，每层从左到右遍历
代码实现：
这里我们利用队列其先进先出的性质，实现层序遍历
队列：
// Queue.h #pragma once #include <stdio.h> #include <stdbool.h> #include <assert.h> #include <stdlib.h> // 前置声明 struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); // 队尾入 void QueuePush(Queue* pq, QDataType x); // 队头出 void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); //Queue.c #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } // 队尾入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); 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; } } // 队头出 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); // 1、一个 // 2、多个 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { ++size; cur = cur->next; } return size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
层序遍历:
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root != NULL) QueuePush(&q, root); while (!QueueEmpty(&q)) //队列不为空则继续 { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c", front->data); if (front->left) //if左边不为空 { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); QueueDestory(&q); } int main() { BTNode* root; LevelOrder(root); }
本节完
