🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
重要提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。
因此，不同的场景我们选择不同的数据结构。
前言：本篇文章，我们继续来看二叉树相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们将正式开始学习第二部分中的二叉树部分内容啦。
注意，二叉树的学习需要一定的基础，涉及到【函数栈帧的创建与销毁】，而且二叉树尤其是链式结构二叉树基本上是递归算法的暴力美学。
【深入详解】函数栈帧的创建与销毁：寄存器、压栈、出栈、调用、回收空间
目录
正文
四、二叉树的链式结构
二叉树分为空树和非空二叉树，非空二叉树由根结点、根结点的左子树、根结点的右子树组成的。
根结点(root)的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的，因此二叉树定义是递归式的，后序链式二叉树的操作中基本都是按照该概念实现的。
（一）前中后序遍历
二叉树操作自然离不开树的遍历，我们来了解一下有哪几种遍历方式——
光看这个概念没什么感觉，我们来举一个例子大家就理解了——
前序遍历（PreOrder）：也叫先根遍历，先遍历根节点，再遍历左子树，最后遍历右子树。
（前序遍历口诀：根左右）
中序遍历（Inorder）：先遍历左子树，再遍历根节点，最后遍历右子树。
（中序遍历口诀：左根右）
后序遍历（Postorder）：先遍历左子树，再遍历右子树，最后遍历根节点。
（后序遍历口诀：左右根）
层序遍历：按照层次依次遍历（从上到下，从左到右）。
上面的例子太简单了，我们举一个复杂一点的例子——
前序遍历：A B D NULL NULL NULL C E NULL NULL F NULL NULL
（A B D C E F）
中序遍历：NULL D NULL B NULL A NULL E NULL C NULL F NULL
（D B A E C F）
后序遍历：NULL NULL D NULL B NULL NULL E NULL NULL F C A
（D B E F C A）
怎么样，做对了吗？只要记住这三个口诀：
根左右、左根右、左右根即可。
（二）递归过程分析
我们来详细分析一下前序遍历的过程——
下面两张图是对应的：
接下来我们来画一下前序遍历的完整过程：
中序遍历：
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
过程差别不大，这里就不再重复了。
后序遍历：
//后序遍历——左右根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
（三）链式结构的实现
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
代码中的BinaryTree就是二叉树的意思。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
下面我们来实现一下链式结构：
还是根据下面这张图，我们来写一写用链表实现的链式结构的代码——
二叉树的创建方式比较复杂，我们根据上图手动创建一棵链式二叉树——
1、手动创建一棵链式二叉树
Tree.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}BTNode;Tree.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
test.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
int main()
{
return 0;
}2、 前中后序遍历
Tree.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}BTNode;
//前序遍历
void PerOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);Tree.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//前序遍历————口诀：根左右
void PerOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PerOrder(root->left);
PerOrder(root->right);
}
//中序遍历——左根右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
//后序遍历——左右根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}test.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
BTNode* buyNode(char x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if ( x == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
void test01()
{
BTNode* nodeA = buyNode('A');
BTNode* nodeB = buyNode('B');
BTNode* nodeC = buyNode('C');
BTNode* nodeD = buyNode('D');
BTNode* nodeE = buyNode('E');
BTNode* nodeF = buyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
//PerOrder(nodeA);
//InOrder(nodeA);
PostOrder(nodeA);
}
int main()
{
test01();
return 0;
}结尾
往期回顾：
函数栈帧的创建与销毁和函数的递归相关博客的链接，博主都已经放在正文前面了，有需要的友友自取。
本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。
大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：
【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）
结语：本篇文章到这里就结束了，对数据结构的二叉树知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！