二叉树的概念及结构
每个结点最多有两颗子树，即二叉树不存在度大于 2 的结点。
任何一颗二叉树可以看成三个部分：①根节点②左子树③右子树
遍历的三种方法
以下面的二叉树为例介绍遍历的方法。
图片.png
先序遍历（前序）
先序遍历的方法是：“根左右”依次遍历，即先访问根结点，再访问左子树，再访问右子树。
以上面的二叉树为例，肯定要先访问根结点 A，然后访问左子树，但 A 的左子树是以 B 为根结点的一颗子树，如下图。
图片.png
那么在这颗子树里我们又要根据“根左右”进行遍历，先访问根结点 B，然后左子树 D，但在这我想让你思考 D 还有没有子树？看样子是没有，不过严格意义我们可以写上 NULL（空），然后就是 B 的右子树，结点 E。
到此为止 A 的左子树已经访问完了，可以写 A B D NULL NULL E NULL NULL，有时候题目不要求我们写空的话，可以直接写 ABDE（接下来为了方便大家看我就不写 NULL 了）。
然后再访问 A 的右子树 C。
先序遍历完成，顺序为：ABDEC
中序遍历
中序遍历的方法是：“左根右”依次遍历，即先访问左子树，再访问根结点，再访问右子树。
以上面二叉树为例，先看 A 有无左子树，有！是根结点为 B 的子树！ 再看 B 有无左子树，有！是结点 D。
D 还有左子树吗？没有，是 NULL（空，我们这里暂且不算）那就先访问 D，然后 D 作为 B 的左子树，接下来就该访问根结点 B。
接着访问 B 的右子树 E，E 有左子树吗？没有。现在我们看到 A 的所有左子树已经遍历完了，接着就是访问根结点 A。
到此为止的顺序为：DBEA
然后再访问 A 的右结点 C。
所以中序遍历的顺序为：DBEAC
可以自己试着把空（NULL）也给算上写出中序遍历：
NULL D NULL B NULL E NULL A NULL C NULL
后序遍历
后序遍历的方法是：“左右根”依次遍历，即先访问左子树，再访问右子树，再访问根结点。
以上面二叉树为例，先看 A 有无左子树，有！是根结点为 B 的子树！ 再看 B 有无左子树，有！是结点 D。D 无子树了，再看 B 是否有右子树，有！是结点 E。
好的那就先访问 D 和 E，然后再访问 B，接着就是 A 的右子树。然后 A 的右子树只有一个 C，最后再访问 A，访问完毕。
后序遍历的顺序为：DEBCA
遍历例题
写出下面二叉树的三种遍历结果
图片.png
严格上可以写 NULL，读者可以自己加以理解，大多数情况会忽略 NULL。
前序遍历：A B NULL D F NULL NULL NULL C E NULL NULL NULL
中序遍历：B F D A E C
后序遍历：F D B E C A
三种遍历方法的代码实现
结构体的定义
typedef char BTDataType;typedef struct BinaryTreeNode{ struct BinaryTreeNode* left; //左孩子 struct BinaryTreeNode* right; //右孩子 BTDataType data;}BTNode;
复制代码
解释：
①typedef char BTDataType; 是将 char 字符类型重新命名为 BTDataType，目的是为了方便代码的可维护性，比如我后面发现 char 不是我想要的类型了，但我已经打了好几个 char 了，就不方便更改了。而用此方法，只需要把 typedef char BTDataType 里的 char 改成 int 就行。
②下面是结构体的定义
前序遍历代码实现
void PrevOrder(BTNode* root) //前序遍历{ if (root == NULL) //空树 return; printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right);}
复制代码
这里就是先打印根结点，毕竟这是前序遍历，然后就访问左子树，即 root->left。
如果遍历的时候想严格打印 NULL 那么就这样写.
void PrevOrder(BTNode* root) //前序遍历{ if (root == NULL) //空树 { printf("NULL "); return; } printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right);}
复制代码
中序遍历代码实现
void InOrder(BTNode* root) //中序遍历{ if (root == NULL) //空树 return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right);}
复制代码
后序遍历代码实现
void PostOrder(BTNode* root) //后序遍历{ if (root == NULL) //空树 return; PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data);}
复制代码
所有函数和 main 函数
#include<stdio.h>#include<stdlib.h>typedef char BTDataType;typedef struct BinaryTreeNode{ struct BinaryTreeNode* left; //左孩子 struct BinaryTreeNode* right; //右孩子 BTDataType data;}BTNode; void PrevOrder(BTNode* root) //前序遍历{ if (root == NULL) //空树 return; printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right);} void InOrder(BTNode* root) //中序遍历{ if (root == NULL) //空树 return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right);} void PostOrder(BTNode* root) //后序遍历{ if (root == NULL) //空树 return; PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data);} int main(){ BTNode* A = (BTNode*)malloc(sizeof(BTNode)); A->data = 'A'; A->left = NULL; A->right = NULL; BTNode* B = (BTNode*)malloc(sizeof(BTNode)); B->data = 'B'; B->left = NULL; B->right = NULL; BTNode* C = (BTNode*)malloc(sizeof(BTNode)); C->data = 'C'; C->left = NULL; C->right = NULL; BTNode* D = (BTNode*)malloc(sizeof(BTNode)); D->data = 'D'; D->left = NULL; D->right = NULL; BTNode* E = (BTNode*)malloc(sizeof(BTNode)); E->data = 'E'; E->left = NULL; E->right = NULL; A->left = B; A->right = C; B->left = D; B->right = E; PrevOrder(A); printf("\n"); InOrder(A); printf("\n"); PostOrder(A); printf("\n"); printf(""); return 0;}
复制代码
这里还是以最上面的二叉树为例。
主函数里我使用了动态内存开辟，使用一次就开一次，不要浪费内存。
评论