写在前面

首先二叉树是一个大家族，这篇文章就讲一讲二叉树的遍历：

递归遍历

迭代遍历

先识概念

二叉树的存储结构，可以为顺序存储，即使用数组；也可以为链式存储，即使用链表。我们使用较多的就是链式存储结构，本篇文章就主要讲解链式存储结构

对于一些最基础的概念，这里就不过多的介绍了，大家还是翻书为妙。

再会做题

大家一定会遇到这样的题目，根据前序遍历和中序遍历，写出后序遍历。或者根据中序遍历和后序遍历写出前序遍历。（前提都是先直到中序遍历）。下面是一些比较容易理解up的视频讲解。

根据二叉图写前中后遍历

看图遍历二叉树_法一

看图遍历二叉树_法二

根据遍历结果画二叉图

常规方法

技巧方法

如果你想解决上面的问题，就不妨将这两种题型结合起来，就能完成“根据前序和中序写后序，根据中序后序写前序“这一类问题了！

学习思想

链式存储结构

//二叉树的链式存储结构
struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
};

二叉树的遍历（递归法）

//前序遍历
void preorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回printf("%d ", root->val);  // 先访问根节点preorderTraversal(root->left);  // 再递归遍历左子树preorderTraversal(root->right);  // 最后递归遍历右子树
}//中序遍历
void inorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回inorderTraversal(root->left);  // 先递归遍历左子树printf("%d ", root->val);  // 再访问根节点inorderTraversal(root->right);  // 最后递归遍历右子树
}//后序遍历
void postorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回postorderTraversal(root->left);  // 先递归遍历左子树postorderTraversal(root->right);  // 再递归遍历右子树printf("%d ", root->val);  // 最后访问根节点
}//层序遍历
int getDepth(TreeNode* root)
{if (root == NULL){return 0;}int left_depth = getDepth(root->left);int right_depth = getDepth(root->right);return (left_depth > right_depth) ? (left_depth + 1) : (right_depth + 1);
}void levelOrderHelper(TreeNode* root, int level)
{if (root == NULL){return;}if (level == 1){printf("%d ", root->val);}else if (level > 1){levelOrderHelper(root->left, level - 1);levelOrderHelper(root->right, level - 1);}
}void levelOrder(TreeNode* root)
{int depth = getDepth(root);for (int i = 1; i <= depth; i++){levelOrderHelper(root, i);}
}

二叉树的迭代遍历（非递归）

二叉树的迭代遍历其实还是不太好理解的，先掌握递归遍历为好

void preorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;struct TreeNode* stack[1000];int top = -1;stack[++top] = root;while (top >= 0) {struct TreeNode* node = stack[top--];printf("%d ", node->val);if (node->right) stack[++top] = node->right;if (node->left) stack[++top] = node->left;}
}/*
1.创建一个栈，将根节点压入栈中。
2.当栈不为空时，弹出栈顶元素，访问该节点。
3.如果该节点的右孩子不为空，将右孩子压入栈中。
4.如果该节点的左孩子不为空，将左孩子压入栈中。
5.重复步骤2到4，直到栈为空。
*/
void inorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;struct TreeNode* stack[1000];int top = -1;struct TreeNode* node = root;while (top >= 0 || node) {while (node) {stack[++top] = node;node = node->left;}node = stack[top--];printf("%d ", node->val);node = node->right;}
}
/*
1.如果根节点为空，直接返回；
2.初始化栈，并将根节点入栈；
3.只要栈不为空，就一直执行以下操作：a. 将当前节点的所有左子节点都入栈，直到左子树为空；b. 取出栈顶元素，输出其值，并将当前节点指向其右子节点；c. 如果右子节点不为空，将其入栈。
*///后序遍历法一
void postorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;struct TreeNode* stack[1000];int top = -1;struct TreeNode* node = root;struct TreeNode* prev = NULL;while (top >= 0 || node) {while (node) {stack[++top] = node;node = node->left;}node = stack[top];if (node->right == NULL || node->right == prev) {printf("%d ", node->val);prev = node;node = NULL;--top;}else {node = node->right;}}
}
/*
1.定义一个栈和两个指针node、prev，其中node指向当前节点，prev指向上一次访问的节点。
2.如果node不为NULL，就将node入栈，并更新node为其左子节点，直到node为NULL。
3.此时stack顶部节点为左子树遍历的最后一个节点。如果stack顶部节点没有右子节点，或者其右子节点已经被访问过了（即右子节点为prev），则可以访问该节点，否则需要访问其右子节点，因此将node指向其右子节点。
4.循环执行上述步骤，直到stack为空。在遍历过程中，如果节点没有左右子节点，则可以直接访问；如果有左右子节点，则需要先遍历左右子树，最后才能访问根节点。因此在访问节点之前，需要判断该节点的左右子树是否已经被访问过，如果已经被访问过，则可以直接访问该节点，否则需要先遍历其左右子树。这就是后序遍历需要特别注意的地方。
*///后序遍历 法二
void postorderTraversal(struct TreeNode* root) {if (root == NULL) return;struct TreeNode* stack1[1000];struct TreeNode* stack2[1000];int top1 = -1, top2 = -1;stack1[++top1] = root;while (top1 >= 0) {struct TreeNode* node = stack1[top1--];stack2[++top2] = node;if (node->left) stack1[++top1] = node->left;if (node->right) stack1[++top1] = node->right;}while (top2 >= 0) {struct TreeNode* node = stack2[top2--];printf("%d ", node->val);}
}/*
它使用了两个栈来实现：
第一个栈用来辅助遍历树的节点；
第二个栈用来按后序遍历的顺序存储节点。1.从根节点开始，依次将左子树的节点入栈；
2.弹出栈顶节点，将其入第二个栈；
3.再依次将右子树的节点入第一个栈；
4.重复步骤 2 和步骤 3，直到第一个栈为空；
5.最后依次弹出第二个栈的节点，并输出它们的值。
*/// 层序遍历
void levelOrder(TreeNode* root) 
{Queue q;initQueue(&q);   //创建队列enqueue(&q, root);  //根结点入队while (!isQueueEmpty(&q))  //如果队列不空{TreeNode* node = dequeue(&q);  //结点出栈并输出printf("%d ", node->val);if (node->left)         //左结点不空，左结点入队{enqueue(&q, node->left);}if (node->right)        //右结点不空，右结点入队{enqueue(&q, node->right);}}
}
/*
将根结点入队，队不空：出栈，打印左结点不空，将左结点入栈右结点不空，将右结点入栈
*/

熟练应用

前中后序遍历——递归

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>//二叉树的链式存储结构
struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
};//二叉树的先序递归创建
struct TreeNode* createTree() 
{int val;scanf("%d", &val);  // 输入当前节点的值，-1表示空节点if (val == -1){return NULL;}else {struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = val;root->left = createTree();  // 递归创建左子树root->right = createTree();  // 递归创建右子树return root;}
}void preorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回printf("%d ", root->val);  // 先访问根节点preorderTraversal(root->left);  // 再递归遍历左子树preorderTraversal(root->right);  // 最后递归遍历右子树
}void inorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回inorderTraversal(root->left);  // 先递归遍历左子树printf("%d ", root->val);  // 再访问根节点inorderTraversal(root->right);  // 最后递归遍历右子树
}void postorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;  // 如果节点为空，返回postorderTraversal(root->left);  // 先递归遍历左子树postorderTraversal(root->right);  // 再递归遍历右子树printf("%d ", root->val);  // 最后访问根节点
}int main() 
{// 递归创建二叉树printf("先序输入二叉树（用 -1 代替 NULL）:\n");struct TreeNode* root = createTree();// 先序遍历二叉树printf("先序遍历: ");preorderTraversal(root);printf("\n");// 中序遍历二叉树printf("中序遍历: ");inorderTraversal(root);printf("\n");// 后序遍历二叉树printf("后序遍历: ");postorderTraversal(root);printf("\n");// 释放内存free(root);return 0;
}

层序遍历——递归

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 定义队列节点
typedef struct QueueNode 
{TreeNode* data;struct QueueNode* next;
} QueueNode;// 定义队列
typedef struct Queue 
{QueueNode* front;QueueNode* rear;
} Queue;// 初始化队列
void initQueue(Queue* q) 
{q->front = NULL;q->rear = NULL;
}// 判断队列是否为空
int isQueueEmpty(Queue* q) 
{return (q->front == NULL);
}// 入队
void enqueue(Queue* q, TreeNode* val) 
{QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->data = val;newNode->next = NULL;if (q->rear == NULL) {q->front = q->rear = newNode;}else {q->rear->next = newNode;q->rear = newNode;}
}// 出队
TreeNode* dequeue(Queue* q) 
{if (isQueueEmpty(q)) {printf("Queue is empty.\n");return NULL;}QueueNode* tempNode = q->front;TreeNode* tempData = q->front->data;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(tempNode);return tempData;
}// 创建二叉树
TreeNode* createBinaryTree() 
{int val;scanf("%d", &val);if (val == -1) {return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = val;root->left = createBinaryTree();root->right = createBinaryTree();return root;
}int getDepth(TreeNode* root)
{if (root == NULL){return 0;}int left_depth = getDepth(root->left);int right_depth = getDepth(root->right);return (left_depth > right_depth) ? (left_depth + 1) : (right_depth + 1);
}void levelOrderHelper(TreeNode* root, int level)
{if (root == NULL){return;}if (level == 1){printf("%d ", root->val);}else if (level > 1){levelOrderHelper(root->left, level - 1);levelOrderHelper(root->right, level - 1);}
}void levelOrder(TreeNode* root)
{int depth = getDepth(root);for (int i = 1; i <= depth; i++){levelOrderHelper(root, i);}
}int main() 
{printf("请输入二叉树节点的值，-1表示空节点：\n");TreeNode* root = createBinaryTree();printf("二叉树层序遍历的结果为：");levelOrder(root);printf("\n");return 0;
}

前中后序遍历——迭代

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>//链式存储结构
struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
};struct TreeNode* createTree() 
{int val;scanf("%d", &val);  // 输入当前节点的值，-1表示空节点if (val == -1) {return NULL;}else {struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = val;root->left = createTree();  // 递归创建左子树root->right = createTree();  // 递归创建右子树return root;}
}void preorderTraversal(struct TreeNode* root) 
{if (root == NULL) return;struct TreeNode* stack[1000];int top = -1;stack[++top] = root;while (top >= 0) {struct TreeNode* node = stack[top--];printf("%d ", node->val);if (node->right) stack[++top] = node->right;if (node->left) stack[++top] = node->left;}
}/*
1.创建一个栈，将根节点压入栈中。
2.当栈不为空时，弹出栈顶元素，访问该节点。
3.如果该节点的右孩子不为空，将右孩子压入栈中。
4.如果该节点的左孩子不为空，将左孩子压入栈中。
5.重复步骤2到4，直到栈为空。
*/
void inorderTraversal(struct TreeNode* root) 
{/*中序非递归遍历，暂且就让结点1的数据为1，结点2的数据为2...1.首先，node指向结点1，此时栈为[ 1 )。下面开始循环2.node不空，node入栈，循环将node的左结点全部入栈，此时node为NULL，此时栈为[ 1 ，2 )。3.出栈，node结点2，打印出数值2，node再指向结点2的右结点，即NULL,此时栈为[ 1 )。4.top>=0可以执行外循环，node为NULL无法执行第二个循环，此时栈还为[ 1 ） 5.出栈，node指向结点1，打印出数值2，node再指向结点1的右结点，即结点3，此时栈为[ )6.node不为空，可以进行外循环和内循环，node及所有左结点入栈，此时栈为[ 3 )7.出栈，node指向结点3，打印出数值3，node再指向结点3的右结点，即NULL，此时栈为[ )8.栈为 NULL，node也为NULL，完美结束外循环，结束程序*/if (root == NULL) return;struct TreeNode* stack[1000];int top = -1;struct TreeNode* node = root;while (top >= 0 || node) {while (node) {stack[++top] = node;node = node->left;}node = stack[top--];printf("%d ", node->val);node = node->right;}
}
/*
1.如果根节点为空，直接返回；
2.初始化栈，并将根节点入栈；
3.只要栈不为空，就一直执行以下操作：a. 将当前节点的所有左子节点都入栈，直到左子树为空；b. 取出栈顶元素，输出其值，并将当前节点指向其右子节点；c. 如果右子节点不为空，将其入栈。
*///后序遍历法二
void postorderTraversal(struct TreeNode* root) {if (root == NULL) return;struct TreeNode* stack1[1000];struct TreeNode* stack2[1000];int top1 = -1, top2 = -1;stack1[++top1] = root;while (top1 >= 0) {struct TreeNode* node = stack1[top1--];stack2[++top2] = node;if (node->left) stack1[++top1] = node->left;if (node->right) stack1[++top1] = node->right;}while (top2 >= 0) {struct TreeNode* node = stack2[top2--];printf("%d ", node->val);}
}/*
它使用了两个栈来实现：
第一个栈用来辅助遍历树的节点；
第二个栈用来按后序遍历的顺序存储节点。1.从根节点开始，依次将左子树的节点入栈；
2.弹出栈顶节点，将其入第二个栈；
3.再依次将右子树的节点入第一个栈；
4.重复步骤 2 和步骤 3，直到第一个栈为空；
5.最后依次弹出第二个栈的节点，并输出它们的值。
*/
int main() 
{// 递归创建二叉树printf("请输入二叉树（用 -1 表示 NULL）:\n");struct TreeNode* root = createTree();// 先序遍历二叉树printf("先序遍历: ");preorderTraversal(root);printf("\n");// 中序遍历二叉树printf("中序遍历: ");inorderTraversal(root);printf("\n");// 后序遍历二叉树printf("后序遍历: ");postorderTraversal(root);printf("\n");// 释放内存free(root);return 0;
}
/*
可以测试输入（ 1 2 -1 -1 3 -1 -1 ）
构建成如下二叉树1/    \2       3/ \     / \-1  -1  -1  -1*/

层序遍历——迭代

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode 
{int val;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 定义队列节点
typedef struct QueueNode 
{TreeNode* data;struct QueueNode* next;
} QueueNode;// 定义队列
typedef struct Queue 
{QueueNode* front;QueueNode* rear;
} Queue;// 初始化队列
void initQueue(Queue* q) 
{q->front = NULL;q->rear = NULL;
}// 判断队列是否为空
int isQueueEmpty(Queue* q) 
{return (q->front == NULL);
}// 入队
void enqueue(Queue* q, TreeNode* val) 
{QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->data = val;newNode->next = NULL;if (q->rear == NULL) {q->front = q->rear = newNode;}else {q->rear->next = newNode;q->rear = newNode;}
}// 出队
TreeNode* dequeue(Queue* q) 
{if (isQueueEmpty(q)) {printf("Queue is empty.\n");return NULL;}QueueNode* tempNode = q->front;TreeNode* tempData = q->front->data;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(tempNode);return tempData;
}// 创建二叉树
TreeNode* createBinaryTree() 
{int val;scanf("%d", &val);if (val == -1) {return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = val;root->left = createBinaryTree();root->right = createBinaryTree();return root;
}// 层序遍历
void levelOrder(TreeNode* root) 
{Queue q;initQueue(&q);enqueue(&q, root);while (!isQueueEmpty(&q)) {TreeNode* node = dequeue(&q);printf("%d ", node->val);if (node->left) {enqueue(&q, node->left);}if (node->right) {enqueue(&q, node->right);}}
}
/*
将根结点入队，队不空：出栈，打印左结点不空，将左结点入栈右结点不空，将右结点入栈
*/int main() 
{printf("请输入二叉树节点的值，-1表示空节点：\n");TreeNode* root = createBinaryTree();printf("二叉树层序遍历的结果为：");levelOrder(root);printf("\n");return 0;
}