前言：在上一篇博客【数据结构】长幼有序：树、二叉树、堆与TOP-K问题的层次解析（含源码）中我们实现了二叉树的顺序结构，在本文中我们将要介绍二叉树的链式结构，通过不断地暴力递归给大家展现链式结构的美学，最后通过经典OJ算法来结束！！！
文章目录
一、二叉树链式结构的介绍
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面在介绍高阶数据结构如红黑树等会用到三叉链
既然我们是通过链式结构来表示二叉树，那么我们可以把二叉树中看成是一个个节点组成，因此我们需要定义一个个节点，而节点是由什么组成？
显而易见：节点由其保存的data数据和其箭头指向的两个孩子。那么孩子节点右又由存储的数据和其两个孩子节点组成，以此内推，我们发现这与递归的核心思想有点关联
根据上面的分析我们来定义下二叉树的节点结构，data是其存储的数据，left是其左孩子节点，right是其右孩子节点
在链式结构中由于其是由指针指向来确定节点的位置，其地址是不确定分散的，这点和顺序结构中用数组存储不同，用数组存储时时类型仅为完全二叉树和满二叉树，这是因为数组的空间是连续的，会导致空间的浪费，而在链式结构中则没有限制，所有类型二叉树均可使用（度为2即可）
二、接口的代码实现
在前面的各种类型的数据结构中我们都实现了插入删除接口，但在这里我们并不会实现，因为链式结构的对应的是普通二叉树，其没有对节点的位置、值的关系等进行约束，导致插入删除操作变得 随意且无价值，后面我们会在平衡树里介绍插入和删除
二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式
1.手动构造二叉树
如上图我们需要
1.为二叉树中的每个节点申请空间来存放data和左右孩子，初始情况left=right=NULL,
2.将二叉树中所有申请好的节点连接在一起，即 nodeA->left = nodeB，nodeA->right =nodeC等等
3.最后返回根节点A即可（只要知道根节点就可以找到其余节点）
BTNode* buyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail!\n");
exit(1);
}
node->data = x;
node->left = node->right = NULL;
return node;
}
//手动构造一棵二叉树
BTNode* CreateTree()
{
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;
return nodeA;
}
2.前序遍历
这里的前序遍历是指的根节点位置是排在最前面，其次是左节点，最后是右节点（注意这几种遍历方式只改变根节点的顺序，左节点遍历的顺序永远是在右节点前面，这个是不会改变的），因此前序遍历简而言之：顺序为 根——左——右
根据上图，我们从根节点A（入口）进来，打印A，然后遍历其的左节点B，发现以B为根节点的左子树也满足根——左——右结构则打印根节点B，我们继续以前序遍历方式来进行，走到B的左孩子D，D也是根节点则继续打印D，我们发现D的左孩子为空，因为不能以空为根节点，所以不能往下找了，打印左节点即可，然后我们回到D这个根节点，发现左孩子打印了，那么再打印下右孩子NULL，打印完后，以D为根节点的子树便打印完了，那么我们继续往上走回到以B为根节点的二叉树，我们发现B的根节点和左孩子打印完了，那么打印右孩子即可，打印完后以B为根节点就完成了，我能继续往上走走到A为根节点处，发现A和B打印完了，因此需要打印右孩子C，而以C为根节点的右子树和左子树流程是一样的。
因此前序遍历的最终结果为：
A——>B——>D——>NULL——>NULL——>NULL——>C——>E——>NULL——>NULL——>F——>NULL——>NULL
代码逻辑：
1.边界判断：终止递归的条件：
若当前传入的根节点 root 为 NULL（即空节点），说明已抵达树的边界，无法继续向下遍历左 / 右孩子。此时直接打印 "NULL " 标记空节点，并通过 return 结束当前递归调用（释放当前函数栈帧），避免对空指针的非法访问。
2.访问当前节点：打印根节点数据：
若 root 不为空，首先打印当前节点的数据（root->data），这是前序遍历 “根 → 左 → 右” 顺序中 “访问根节点” 的步骤
3.递归遍历左右子树：深度优先的递进与回溯：
完成根节点的打印后，递归调用 PreOrder(root->left) 遍历左子树。这一过程会持续深入左子树：例如从节点 B 递归到节点 D，再从 D 递归其左孩子（NULL）。当 D 的左孩子为 NULL 时，触发步骤 1 的逻辑（打印 "NULL " 并 return），此时 PreOrder(D->left) 的函数栈帧释放，程序回到 D 节点的函数栈帧中。
左子树遍历完毕后，继续递归调用 PreOrder(root->right) 遍历右子树。
例如 D 的左子树处理完后，递归其右孩子（仍为 NULL），同样打印 "NULL " 并 return，释放 PreOrder(D->right) 的栈帧，回到 D 节点的函数栈帧。
当 D 的左、右子树均遍历完成（即 PreOrder(D->left) 和 PreOrder(D->right) 均执行完毕），D 节点的函数栈帧释放，程序回溯到其双亲节点 B 的函数栈帧中，继续处理 B 的右子树。
以此类推，直到整棵树的根节点（如 A）的左、右子树均遍历完成，所有递归栈帧释放，遍历结束。
具体实现图片如下：
代码实现：
void PreOrder(BTNode* root)
{
//如果根节点为空，则不能往下遍历
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
3.中序遍历
中序遍历根据前面的解释可知，指的是根节点在中间，因此顺序为：左——根——右
中序遍历思想和前序遍历类似，这里不继续解释
中序遍历的最终结果为:
NULL——>D——>NULL——>B——>NULL——>A——>NULL——>E——>NULL——>C——>NULL——>F——>NULL
代码逻辑： 在前序遍历中已经解释了，这里和上面的思想是大同小异
代码实现：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
4.后序遍历
后序遍历指的是根节点在最后面，因此顺序为;左——右——根
后续遍历的最终结果为：
NULL——>NULL——>D——>NULL——>B——>NULL——>NULL——>E——>NULL——>NULL——>F——>C——>A
代码实现;
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
5.二叉树的节点个数
思路1:定义局部变量size初始为0，遍历二叉树（递归调用），只要节点不为NULL便让size++，但是每次递归进入函数，会创建新的函数栈帧，每次都会初始化size为0，因此该方法不行
思路2：定义全局变量size，我们期待的结果是6个节点，实际打印结果如下图：
这里size结果为6，看似是正确的，符合预期，如果我们再打印一次预期结果应该还是6，但是实际打印结果如下：12，我们发现全局变量在调用的时候一直在累加（++），因此全局变量和局部变量均不行。
因此我们试了static静态变量也是下面结果
代码如下：
// ⼆叉树结点个数
// 这里不能定义全局变量，如果在主函数中调用了两次，第一次打印6，第二次打印12，依次递增，
// 局部变量也不行，每次函数递归的时候，局部变量会从0重新赋值
// 静态变量也不行，递归调用时候还是会增加，变成6,12
//
int BinaryTreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
{
return 0;
}
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}
结果如下：
那么如果我们在函数的变量中传入size可行吗？
代码如下：
//错误
void BinaryTreeSize(BTNode* root, int size)
{
if (root == NULL)
{
return 0;
}
++size;
BinaryTreeSize(root->left,size);
BinaryTreeSize(root->right,size);
return size;
}
运行结果如下:
我们发现更加不对了，为啥size会变成1？
因为函数参数采用值传递，每次递归调用的size都是独立副本，无法实现跨栈帧的累加
当调用函数时，size作为参数按值传递，每个递归栈帧都会创建一个独立的size副本。对当前栈帧中size的修改，仅影响当前帧，不会同步到上层或下层栈帧
结论：传递无法实现跨栈帧累加
1.每个递归栈帧的size是独立副本，修改仅在当前帧有效，无法向上层或下层传递
2.最终上层栈帧（如 A 的栈帧）的size只记录了自身的一次递增（从 0 到 1），因此结果为 1
那么我们传入size的地址可以实现吗？
代码如下：
//错误
void BinaryTreeSize(BTNode* root, int* psize)
{
if (root == NULL)
{
return 0;
}
++(*psize);
BinaryTreeSize(root->left,psize);
BinaryTreeSize(root->right,psize);
return psize;
}
运行结果如下：
结果还是不对，size依旧被累加，那我们该如何实现？
正确思路：
1.前置条件：根节点为NULL，直接return 0
2.求二叉树节点个数=根节点+左子树节点个数+右子树节点个数
3.因此我们不断递归即可
代码实现：
//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
//要求二叉树节点的个数为：根节点1 +左子树节点的个数+ 右子树节点的个数
//然后左子树节点的个数等于：根节点1 +左子树节点的个数+ 右子树节点的个数，同理右子树一样，依次递归调用，我们最后得到二叉树总节点个数
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
6.二叉树叶子结点的个数
思路：这里和求节点个数类似，均是递归调用，公式为：叶子节点个数=左子树节点个数+右子树节点个数，但是我们要考虑前置条件
1.根节点为空，返回0
2.叶子节点的条件是没有左右孩子即left=right=NULL
3.递归调用函数返回左子树叶子节点个数+右子树叶子结点个数
代码实现：
/ ⼆叉树叶⼦结点个数
//即左子树节点个数+右子树节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
7.二叉树第k层节点个数
思路： 假设我们要 求第二层节点个数，即k=2，那么在给定的函数int BinaryTreeLevelKSize(BTNode* root, int k)中，即根节点·对应的是k=2，那么 求第二层则让k–直至k=1为止，这里k是一个递减计数器，每递归一层就减 1，表示 “距离目标层还剩多少层“，当 k 减至 1 时，说明当前层就是目标层，直接返回 1（当前节点存在），然后我们递归调用函数即可
前置条件：
1.根节点为空返回NULL
2.如果k=1，无论二叉树树的结构如何，第 1 层节点数恒为 1（根节点）
注意：这里的k不需要传地址，因为k 的变化是 “局部且独立” 的，不需要影响其他递归分支，如若传地址则会让所有递归分支共享同一个 k 。例如：
左子树将 k 从 3 减到 2，右子树的 k 也会变成 2，而不是保持初始的 3，最终结果错误
代码实现：
// ⼆叉树第k层结点个数=左子树第k层节点的个数+右子树第k层节点的个数，如果是第一层即根节点，那么不涉及递归。
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
8.二叉树的高度/深度
思路: 这里我们求解高度是： 根节点层次+（左子树，右子树）MAX的层次，依然是递归调用，最后使用三目操作符来比较左子树和右子树中得到层次最大的一个子树+1得到最后二叉树的高度
代码实现：
//⼆叉树的深度/⾼度
//高度=根节点的层次+ max（左子树,右子树)中最大的层次
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDep = BinaryTreeDepth(root->left);
int rightDep = BinaryTreeDepth(root->right);
return 1 + (leftDep > rightDep ? leftDep : rightDep);
}
9.二叉树查找值为x的结点
前置条件判断：
1.若根节点为空，无法找到x，直接返回NULL
2.若根节点存储的数据时x，则返回根节点
3.上述情况均不是，则先遍历左子树，找到了则返回，若没有找到，则再去遍历右子树
4.若左右子树均没有找到，则不存在直接返回NULL
代码实现：
// ⼆叉树查找值为x的结点
//遍历：先遍历左子树，
// 找到了，直接返回
// 没找到，再去遍历右子树
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftFind = BinaryTreeFind(root->left, x);
if (leftFind)
{
return leftFind;
}
BTNode* rightFind = BinaryTreeFind(root->right, x);
if (rightFind)
{
return rightFind;
}
return NULL;
}
10.二叉树的销毁
思路：注意这里传的是二级指针，是为了销毁并将根节点置为空，上面的接口传一级指针是因为不用修改二叉树，这里依旧是递归调用依次进行释放节点（这里形参的改变要影响实现的改变）
代码实现：
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
11.层序遍历
层序遍历见名知意就是一层一层遍历，遍历顺序为：
A——>B——>C——>D——>E——>F
这里我们发现二叉树的遍历方式是用不了了的，如:遍历左节点的同时存储右节点也是不行。那么我思考有没有一种遍历方法可以实现？
这里我们借用数据结构——队列：
思路： 借用数据结构——队列：根节点入数据，循环判断队列是否为空，不为空取并出队头节点，将节点的左右孩子入队列
1.将二叉树的根节点A（是节点不是节点里面的数据）入到队尾中
2.这时队列不为空，不为空，则将队列的队头数据A拿出来
3.那么根节点A有左右孩子，那么就让左右孩子B,C先后入队列
123步骤如下图1：
4.当前队列不为空，取出队头节点B出队列，再看B有D孩子，那么就让D入队列
5.继续判断当前队列不为空，则取队头节点C出队列,C有E,F孩子，让E,F依次入队列
6.继续判断队列不为空，取队头D出队列，D没有左右孩子，则不入队列
7.再判断队列不为空，取队头E，没有左右孩子，依次进行直至F出队列
8.最后打印完的结果为：A——>B——>C——>D——>E——>F
代码实现：
//层序遍历
void LevelOrder(BTNode* root)
{
//借助数据结构---队列
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队列
BTNode* top = QueueFront(&q);
QueuePop(&q);
printf("%c ", top->data);
//将队头左右孩子入队列（不为空）
if (top->left)
{
QueuePush(&q, top->left);
}
if (top->right)
{
QueuePush(&q, top->right);
}
}
QueueDestroy(&q);
}
12.判断二叉树是否为完全二叉树
完全二叉树： 最后一层节点的个数不一定达到最大，节点从左到右依次排列
上图则不是完全二叉树，因为节点不是从左到右依次排列
思路： 我们要判断除最后一层外的每一层的节点个数是否为最大，这里需要遍历层，那么还是要使用队列来实现
1.初始化队列：将二叉树的根节点入队，若根节点为空，则该树是完全二叉树
2.开始遍历：从队列中取出队头节点，判断其是否为空
若当前节点不为空，将其左孩子和右孩子依次入队（无论孩子是否为空），继续取下一个节点。
若当前节点为空，说明已到达 “空节点区域”，此时停止取出节点，转而检查队列中剩余的节点
3.检查剩余节点：若队列中剩余的节点全为空，则该二叉树是完全二叉树；若存在非空节点，则不是完全二叉树
注意: 最重要的便是第3点，在第二个循环里面存在不为空的节点则不是完全二叉树
代码实现：
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
//最后一层节点的个数不一定达到最大
//节点从左到右依次排列
//完全二叉树：第二个循环中剩下的所有的节点都为空
//非完全二叉树：第二个循环中存在不为空的节点
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top == NULL)
{
break;
}
//把不为空的队头节点的左右孩子入队列
QueuePush(&q, top->left);
QueuePush(&q, top->right);
}
//队列不一定为空，继续取队头出队头
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top != NULL)
{
//代码返回之前一定要销毁队列
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
三、最全接口源码
最全接口源码
四、经典OJ题
1.单值二叉树
题目解释： 二叉树中的所有节点存储的数据都是相同的
思路：
1.如果root为空返回true
2.如果root非空我们就判断其左右孩子不为空时值是否跟根结点值相等，如果不相等就返回false
3.我们需要递归判断子树和右子树是否都为单值二叉树
代码实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) {
if(root==NULL)
{
return true;
}
//节点不为空，就拿节点和其左右节点的值进行比较
//左孩子和根节点比较
if(root->left&&root->val!= root->left->val)
{
return false;
}
//右孩子和根节点比较
if(root->right&&root->val!=root->right->val)
{
return false;
}
//当前根节点和左右节点的值相同
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
2.相同的树
题目解释： 两棵树的结构相同且存储的值也一样
如示例1，返回true
示例2： 两棵树的结构分别为：根——左 ，根——右，因此返回false
示例3：虽然结构相同，但是节点存储的值不同，返回false
根据下面的提示可知，任意一棵树可以为空，或者都为空的可能
思路：
1.如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
2.如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同，直至子树不同返回false，或者为空，返回true
代码实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL && q==NULL)
{
return true;
}
if(p==NULL||q==NULL)
{
return false;
}
//p和q都不为空
if(p->val!=q->val)
{
return false;
}
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
3.另一棵树的子树
示:1：
这里可以理解为subRoot就是root子树，类似于集合的包含关系
示例2：
虽然在root里面包含了subRoot的所有节点，但是在subRoot结构里面，2是没有孩子节点，但是在root里面2是有左孩子0，因此不是子树关系
思路： 这里让root的根节点3和subRoot进行比较，判断是否是相同的树，这个方法在第二题已经实现了，直接拿过来调用即可，若干相同，则不需要递归直接返回true，如果不相同，则让root向下递归，拿root左子树和subRoot比较，相同就直接返回true，同理右子树也是如此，因此左右子树的关系是或者关系。如果root最后传为空，那么肯定不是相同子树，直接返回false
代码实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL && q==NULL)
{
return true;
}
if(p==NULL||q==NULL)
{
return false;
}
//p和q都不为空
if(p->val!=q->val)
{
return false;
}
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if(root==NULL)
{
return false;
}
if(isSameTree(root,subRoot))
{
return true;
}
//root和subroot不是相同的树-----subroot不是root的子树
//继续递归
return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
总结
1 . 二叉树链式结构的递归之美，在于 “以简驭繁” 的暴力哲学
2 .每个链式节点都是子树的根，递归让我们无需纠结全局，只需聚焦 “当前节点该做什么”—— 遍历、计数、判断，剩下的交给子树递归即可。前序、中序、后序遍历仅差 “根节点访问时机”，节点统计靠 “1 + 左 + 右” 的递归公式，核心逻辑高度统一。
3 .这种 “暴力” 不是蛮干，而是借链式结构的自相似性，用重复的单节点逻辑拆解复杂树结构。简单递归生复杂，重复操作显秩序，这便是链式二叉树最精妙的美学
4 .通过经典OJ感受递归暴力美学的思想