1. 背景
在上一篇中，已经构造了一个二叉树，并且对其进行了遍历输出，实际上处于不同的需求，对二叉树节点的遍历顺序有不同的做法，本文就研究下最常用的二叉树的四种遍历算法。
先给一个标准的二叉树：
2. 前序遍历
前表示前面、先前的意思，序是顺序的意思，前序遍历是指根节点的访问顺序是在前面的，所以：
前序遍历：总是先访问根节点、然后访问左子树、然后访问右子树
1
所以对于上面的二叉树，前序遍历顺序为：A-B-D-E-C-F-G
3. 中序遍历
中表示的中间的意思，中序遍历是指根节点的访问顺序是在中间的，所以：
中序遍历：总是先访问左子树、然后访问根节点、然后访问右子树
1
所以对于上面的二叉树，中序遍历顺序为：D-B-E-A-F-C-G
4. 后序遍历
后是后面，后来的意思，后续遍历是指根节点的访问顺序是在后面的，所以：
后序遍历：总是先访问左子树、然后访问右子树、然后访问根节点
1
所以对于上面的二叉树，后序遍历顺序为：D-E-B-F-G-C-A
5. 层序遍历
这个好理解，按层次访问，所以：
层序遍历：自上层至下层，同层自左至右遍历
1
所以对于上面的二叉树，层序遍历顺序为：A-B-C-D-E-F-G
6. 代码实现
分析清楚了如何遍历的，代码实现也就水到渠成啦。
#include<stdio.h> /* * 二叉树的前序、中序、后序遍历演示DEMO * 作者：熊猫大大 * 时间：2019-12-08 */ #include <stdio.h> typedef struct { char data;//数据区域(为了保存ABCD，直接用char当做数据域，便于和文章中的插图对应，稳！) struct BinaryTreeNode* left;//左子节点 struct BinaryTreeNode* right;//右子节点 }BinaryTreeNode; //为树的当前节点添加左子节点 int addLeftChild(BinaryTreeNode* curNode, char leftData) { //分配新节点 BinaryTreeNode* leftNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 leftNode->data = leftData; //新节点暂时无子节点 leftNode->left = NULL; leftNode->right = NULL; //将新节点挂到当前节点下 curNode->left = leftNode; return 1; } //为树的当前节点添加右子节点 int addRightChild(BinaryTreeNode* curNode, char rightData) { //分配新节点 BinaryTreeNode* rightNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 rightNode->data = rightData; //新节点暂时无子节点 rightNode->left = NULL; rightNode->right = NULL; //将新节点挂到当前节点下 curNode->right = rightNode; return 1; } // 前序遍历，根--左--右 void preOrder(BinaryTreeNode *node) { if (node == NULL) { return; } printf("%c ", node->data); preOrder(node->left); preOrder(node->right); } // 中序遍历，左--根--右 void midOrder(BinaryTreeNode *node) { if (node == NULL) { return; } midOrder(node->left); printf("%c ", node->data); midOrder(node->right); } // 后序遍历，左--根--右 void afterOrder(BinaryTreeNode *node) { if (node == NULL) { return; } afterOrder(node->left); afterOrder(node->right); printf("%c ", node->data); } //----------------------------------------------------------------------------------------------------测试入口区域 int main() { //设定根节点 BinaryTreeNode root; //根节点A root.data = 'A'; addLeftChild(&root, 'B'); addRightChild(&root, 'C'); //为B节点增加子节点 addLeftChild(root.left, 'D'); addRightChild(root.left, 'E'); //为C节点增加子节点 addLeftChild(root.right, 'F'); addRightChild(root.right, 'G'); printf("\n前序遍历："); preOrder(&root); printf("\n中序遍历："); midOrder(&root); printf("\n后序遍历："); afterOrder(&root); return 1; }
PS：层序遍历有点复杂，后续实现。