theme: smartblue
携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第4天，点击查看活动详情
二叉树的概念及结构
每个结点最多有两颗子树，即二叉树不存在度大于2的结点。
任何一颗二叉树可以看成三个部分：①根节点②左子树③右子树
遍历的三种方法
以下面的二叉树为例介绍遍历的方法。
先序遍历（前序）
先序遍历的方法是：“根左右”依次遍历，即先访问根结点，再访问左子树，再访问右子树。
以上面的二叉树为例，肯定要先访问根结点A，然后访问左子树，但A的左子树是以B为根结点的一颗子树，如下图。
那么在这颗子树里我们又要根据“根左右”进行遍历，先访问根结点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
遍历例题
写出下面二叉树的三种遍历结果
严格上可以写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就行。
②下面是结构体的定义，对结构体不太明白的读者可以阅读C语言结构体 - 掘金 (juejin.cn)
前序遍历代码实现
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;
}
这里还是以最上面的二叉树为例。
主函数里我使用了动态内存开辟，使用一次就开一次，不要浪费内存。