【数据结构】感受递归暴力美学：链式二叉树全方位剖析（附源码）

🔥

@晨非辰Tong： 个人主页
👀专栏：《C语言》、《数据结构与算法入门指南》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”

文章目录

• **引言**
• 一、介绍链式二叉树
  • 1.1 概念
  • 1.2 基本结构（结构上的递归性）
• 二、遍历接口实现（操作上的递归性）
  • 2.1 前序遍历（根左右）
    • 1. 概念
    • 2. 代码
  • 2.2 中序遍历（左根右）
    • 1. 概念
    • 2.代码
  • 2.3 后序遍历
    • 1. 概念
    • 2. 代码
• 三、其余接口实现（操作上的递归性）
  • 3.1 构造二叉树
    • 1. 概念
    • 2. 代码
  • 3.2 树的有效节点个数
    • 1. 概念
    • 2. 代码
      • 2.1 正确方法
    • 2.2 错误方法：创建全局变量/静态修饰
    • 2.3 低效率方法：传参
  • 3.3 二叉树叶子节点个数
    • 2. 代码
  • 3.4 求第k层节点的个数
    • 1. 概念
    • 2. 代码
  • 3.5 求树的高度/深度
    • 1. 概念
    • 2. 代码
  • 3.6 查找指定数据的节点
  • 3.7 层序遍历
  • 3.8 判断是否为完全二叉树
  • 总结

引言

递归是程序员的必修课，而链式二叉树正是理解递归的绝佳范例。在这篇文章中，你将通过实现二叉树的遍历、统计节点、计算深度等操作，真正掌握递归思维。从令人头疼的“函数自调用”，到游刃有余的递归设计，让我们一起开启这段从递归畏惧者到递归掌控者的蜕变之旅。

一、介绍链式二叉树

1.1 概念

链式结构：是指用链表来表示一颗二叉树，即用链表来指示元素的逻辑关系。 通常链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别指向该节点左孩子和右孩子所在的地址 。

1.2 基本结构（结构上的递归性）

既然链式二叉树是用链表来表示，那么二叉树就是由一个个的节点构成，与前面的队列的实现相同，链式二叉树的结构就是一个节点的结构。

那么，链式二叉树的节点又是由什么构成？根据链式二叉树的概念–>节点由三部分构成：存储数据的变量、指向左孩子节点的指针、指向右孩子节点的指针。

//定义链式二叉树的结构--节点结构typedefint BTDataType;typedefstructBinaryTreeNode{int data;//存储数据structBinaryTreeNode* left;//指针指向左孩子节点（左子树）structBinaryTreeNode* right;//指针指向右孩子节点（右子树）}BTNode;

通过这样节点的结构，将所有节点链接在一起形成一棵树。–观察图示、节点结构，递归结构就此显现：

一个二叉树由三部分组成根节点；左子树 ，它本身也是一个二叉树；右子树 ，它本身也是一个二叉树。

这样的结构定义是“自相似的”，那么再来看–>递归的定义：“递归，就是将问题逐步分解为与原始问题相似的更小规模的子问题，来解决原始问题；直到转化为最简单的子问题，递归调用结束”。

–这也就进一步证实了链式二叉树的结构是递归性质的。

二、遍历接口实现（操作上的递归性）

链式二叉树的结构是递归的，那么对树进行的大多数操作，其算法必然是递归的。处理整个二叉树树和处理它的子树，结构都是相似的，导致使用的是完全相同的方法。

二叉树的遍历都遵循层序遍历：按照层次依次遍历（从上到下、从左到右）。

2.1 前序遍历（根左右）

1. 概念

前序遍历，又称为先根遍历，其遍历规则为：先遍历根节点，再遍历左子树，最后遍历右子树。–> 简记为“根左右”。

根据图解：首先铭记–>根左右规则

从根节点A出发，打印A ——> 进入左子树，打印B，现在以B为节点（根左右） ——> 进入左子树，打印D，现在以D为根节点（根左右）——> 进入左子树，打印NULL，没有子树 ——>

开始递归返回D，进入右子树，打印NULL，没有子树 ——> 递归返回D ，左子树遍历完成 ——> 递归返回B，进入右子树，打印NULL，没有子树 ——> 递归返回B，左子树遍历完成 ——>

递归返回A，进入右子树，打印C，现在以C为根节点（根左右） ——> 进入左子树，打印E，现在以E为根节点（根左右） ——> 进入左子树，打印NULL，没有子树 ——> 递归返回E，进入右子树，打印NULL，没有子树 ——> 递归返回E，左子树遍历完成 ——>

递归返回C，进入右子树，打印F，现在以F为根节点（根左右） ——> 进入左子树，打印NULL，没有字数 ——> 递归返回F，进入右子树，打印NULL，没有子树 ——>

递归返回F，右子树遍历完成 ——> 递归返回C，右子树遍历完成 ——> 递归返回A，遍历结束。

最终遍历结果：A——>B——>D——>NULL——>NULL——>NULL——>C——>E——>NULL——>NULL——>F——>NULL——>NULL

2. 代码

//Tree.c#include"Tree.h"//前序遍历---根左右voidPreOrder(BTNode* root){//如果最开始的根节点就是空，代表没有子树，直接打印空，结束if(root ==NULL){printf("NULL ");return;}printf("%c ", root->data);//根据规则，打印完根节点，对左子树进行前序遍历，递归调用PreOrder(root->left);//根据规则，遍历完左子树，前序遍历右子树，递归调用PreOrder(root->right);}

思路：（对一个简单2层的二叉树）
首先看整个二叉树的根节点是否为空，为空直接输出NULL，结束；不为空，也是先打印根节点数据。
遍历完根节点，对左子树进行前序遍历，在函数内再次调用自己，将根节点的左孩子指针传参，进行递归调用。
前序遍历完左子树，开始对右子树进行前序遍历，再次调用自己（与左子树遍历并列），将根节点的右孩子指针传参，递归调用。

//test.c#include"Tree.h"voidtest01(){//将有效数据申请节点 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;PreOrder(nodeA);}intmain(){test01();return0;}

2.2 中序遍历（左根右）

1. 概念

中序遍历，指的是跟根节点在中间打印，先遍历左子树，再遍历根节点，最后遍历右子树。----> 简记为“左根右”。

根据图解：首先铭记–>左根右规则

从根节点A出发，进入左子树，现在以B为根节点—>进入左子树，现在以D为根节点—>进入左子树，打印NULL，没有子树—>

开始递归返回D，打印D—>进入右子树，打印NULL，没有子树—>递归返回D，左子树遍历完成—>递归返回B，进入右子树，打印NULL，没有子树——>递归返回B，左子树遍历完成—>

遍历返回A，打印A，进入右子树，现在以C为根节点—>进入左子树，现在以E为根节点—>进入左子树，打印NULL，没有子树—>递归返回E，打印E—>进入右子树，打印NULL，没有子树—>递归返回E，左子树遍历完成—>

遍历返回C，打印C—>进入右子树，现在以F为根节点—>进入左子树，打印NULL，没有子树—>递归返回F，打印F—>进入右子树，打印NULL，没有子树—>递归返回F，右子树遍历完成—>

递归返回C，右子树遍历完成—>递归返回A，结束。

最终遍历结果为:NULL——>D——>NULL——>B——>NULL——>A——>NULL——>E——>NULL——>C——>NULL——>F——>NULL

2.代码

//Tree.c文件#include"Tree.h"//中序遍历---左根右voidInOrder(BTNode* root){//如果最开始的根节点就是空，代表没有子树，直接打印空，结束if(root ==NULL){printf("NULL ");return;}//根据规则，先前中遍历左子树InOrder(root->left);//输出根节点printf("%c ", root->data);//最后对右子树进行中序遍历InOrder(root->right);}//________________////test.c文件 include "Tree.h"voidtest01(){//将有效数据申请节点 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;InOrder(nodeA);}intmain(){test01();return0;}

思路：（对一个简单的二叉树）

首先也是先看整个二叉树的根节点是否为空，为空直接输出NULL，结束；

不为空，对左子树进行中序遍历，再次调用自己，将根节点的左孩子指针传参，递归调用。

遍历完左子树，打印根节点数据。

最后对右子树进行中序遍历，也是在函数内再次调用自己，将根节点的右孩子指针传参，进行递归调用。

2.3 后序遍历

1. 概念

后序遍历，指的是跟根节点在最后打印，先遍历左子树，再遍历右子树，最后遍历根节点。----> 简记为“左右根”。

根据图解：首先铭记–>左右根规则

从根节点A出发，进入左子树，现在以B为根节点——>进入左子树，现在以D为根节点——>进入左子树，打印NULL，没有子树——>

开始递归返回D，进入右子树，打印NULL，没有子树——>递归返回D，打印D——>递归返回B，进入右子树，打印NULL，没有子树——>递归返回B，打印B——>

递归返回A，进入右子树，现在以C为根节点——>进入左子树，现在以E为根节点——>进入左子树，打印NULL，没有子树——>递归返回E，进入右子树，打印NULL，没有子树——>递归返回E，打印E——>递归返回C，进入右子树，现在以F为根节点——>进入左子树，打印NULL，没有子树——>递归返回F，进入右子树，打印NULL，没有子树——>

递归返回F，打印F——>递归返回C，打印C——>递归返回A，打印A，结束。

最终遍历结果为：NULL——>NULL——>D——>NULL——>B——>NULL——>NULL——>E——>NULL——>NULL——>F——>C——>A

2. 代码

//Tree.c文件 include "Tree.h"//后序遍历--左右根voidPostOrder(BTNode* root){//如果最开始的根节点就是空，代表没有子树，直接打印空，结束if(root ==NULL){printf("NULL ");return;}//根据规则，先后中遍历左子树PostOrder(root->left);//遍历完左子树，对右子树进行后序遍历PostOrder(root->right);//最后，打印根节点printf("%c ", root->data);}//______________////test.c文件#include"Tree.h"voidtest01(){//将有效数据申请节点 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;PostOrder(nodeA);}intmain(){test01();return0;}

思路：（对一个简单2层的二叉树）

首先也是先看整个二叉树的根节点是否为空，为空，代表树为空，直接输出NULL，结束；

不为空，对左子树进行中序遍历，在函数内再次调用自己，将根节点的左孩子指针传参，进行递归调用。

遍历完左子树，再次递归调用函数，将根节点的右孩子指针传参。

最后打印根节点数据。

三、其余接口实现（操作上的递归性）

为了方便以后接口的实现，现在构造出一个二叉树。

3.1 构造二叉树

1. 概念

像图片这样，以所示二叉树为例： 我们需要申请节点空间存储二叉树中所有有效数据节点，这就需要去动态开辟空间；其次，根据节点之间的父子关系通过指针链接彼此;

2. 代码

//Tree.c#include"Tree.h"//申请节点空间 BTNode*buyNode(char x){ BTNode* newnode =(BTNode*)malloc(sizeof(BTNode)); newnode->data = x; newnode->left = newnode->right =NULL;return newnode;}//创建二叉树 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; nodeB->right = nodeE; nodeC->left = nodeF;return nodeA;}

3.2 树的有效节点个数

1. 概念

遍历二叉树时，只要节点不为空，个数就+1，为空则返回。

树的有效节点个数 = 左子树有效节点个数 + 右子树有效节点个数，根据这个思路就可以将求整体树的节点划分成求一个一个的子树节点在加和，这就是递归思想。

2. 代码

2.1 正确方法

//Tree.c文件#include"Tree.h"//树的有效节点个数//树节点总数 = 1 + 左子树节点个数 + 右子树的节点个数intBinaryTreeSize(BTNode* root){if(root ==NULL){return0;}return1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);}//_____________////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//节点个数printf("size:%d\n",BinaryTreeSize(root));printf("size:%d\n",BinaryTreeSize(root));}intmain(){test01();return0;}

—多次测试，size没有累加，代码运行成功。

2.2 错误方法：创建全局变量/静态修饰

–只展示主要代码。

思路：（对一个简单2层的二叉树）

首先创建变量size统计节点个数，全局变量。

然后先判断根节点是否为空，为空代表没有有效节点，直接返回0；不为空，那么根节点算一个有效节点，size++。

最后，递归调用函数遍历左子树、右子树。

//Tree.c文件、#include"Tree.h"//树的有效节点个数_方法1int size =0;//定义全局变量intBinaryTreeSize(BTNode* root){//根节点为空，即树为空，直接返回结束if(root ==NULL){return0;}//根节点不为空，根节点为有效节点，size+1 size++;//递归调用左子树、右子树BinaryTreeSize(root->left);BinaryTreeSize(root->right);return size;}//_____________////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//节点个数printf("size:%d\n",BinaryTreeSize(root));printf("size:%d\n",BinaryTreeSize(root));}intmain(){test01();return0;}

错误原因：创建局部变量，每次调用函数，变量都被初始化，无法统计。

值得注意的是——>全局变量只被初始化一次，此后对变量的修改都会继承；多次调用函数，变量会继承在上次调用后变量的值。

–那么对变量进行static修饰呢？ --> 也不行！

2.3 低效率方法：传参

//Tree.c文件#include"Tree.h"/树的有效节点个数_方法2//传参intBinaryTreeSize(BTNode* root,int* psize){//根节点为空，即树为空，直接返回结束if(root ==NULL){return0;}//根节点不为空，根节点为有效节点，size+1(*psize)++;//递归调用左子树、右子树BinaryTreeSize(root->left, psize);BinaryTreeSize(root->right, psize);}//____________////test.c文件voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//节点个数int Treeszie =0;BinaryTreeSize(root,&Treeszie);printf("size:%d\n", Treeszie); Treeszie =0;BinaryTreeSize(root,&Treeszie);printf("size:%d\n", Treeszie);}intmain(){test01();return0;}

解析：

将size每次当作参数传给函数，这样避免了变量累加的情况。但是这样接改变了函数的形式，破坏了接口一致性，使用起来不方便。并且在测试时，每次使用前都要手动将变量置零。

3.3 二叉树叶子节点个数

某节点的左、右孩子节点均为NULL时，就叫叶子节点。求二叉树总叶子节点数，就将左右子树的叶子节点加和，这就将大问题分成一个个小问题。
——>总的叶子节点个数 = 左子树叶子节点树 + 右子树叶子节点数。

2. 代码

//Tree.c文件#include"Tree.h"//二叉树的叶子节点个数//总的叶子节点个数 = 左子树叶子节点树 + 右子树叶子节点数intBinaryTreeLeafSize(BTNode* root){//判断整体的根节点if(root ==NULL){return0;}//叶子节点条件，左右子节点均为NULLif(root->left ==NULL&& root->right ==NULL){return1;//叶子节点数+1}//否则继续遍历子树returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}//___________////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//总的叶子节点数printf("leaf size:%d\n",BinaryTreeLeafSize(root));}intmain(){test01();return0;}

3.4 求第k层节点的个数

1. 概念

求第k层的节点个数，要求是有效的节点。

根据参数k，遍历1层就–，到k=1时代表已经到了第k层。第k层节点个数 = 左子树第k层节点个数 + 右子树第k层节点个数。

2. 代码

思路：（对一个简单2层的二叉树）

首先判断根节点是否为空，为空直接返回结束；否则判断是否为k层，是k层则返回1，不是就递推调用函数遍历左右孩子节点（左右子树）。

//Tree.c文件#include“Tree.h”//求第k层节点个数//第k层节点个数 = 左子树第k层节点个数 + 右子树第k层节点个数intBinaryTreeLevelKSize(BTNode* root,int k){//判断整体根节点if(root ==NULL){return0;}if(k ==1){return1;}//否则递归遍历子树returnBinaryTreeLevelKSize(root->left, k-1)+BinaryTreeLevelKSize(root->right, k-1);}//__________////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//求第k层节点个数int k =0;printf("Input level:");scanf("%d",&k);printf("k level size：%d\n",BinaryTreeLevelKSize(root, k));}intmain(){test01();return0;}

3.5 求树的高度/深度

1. 概念

树的深度为有效节点的最大层次。总的高度 = 1（根节点独占1层） + （左右子树中高度最大的）。

2. 代码

思路：

判断根节点；提前保存左、右子树计算出的深度——>方便返回时使用三目操作符，不然需要递归四次，比较繁琐。整体来说，还是比较简单的。

//Tree.c文件#include"Tree.h"//求树的深度/高度intBinaryTreeDepth(BTNode* root){//判断根节点if(root ==NULL){return0;}//提前保存子树高度int leftDeptt =BinaryTreeDepth(root->left);int rightDeptt =BinaryTreeDepth(root->right);return1+(leftDeptt > rightDeptt ? leftDeptt : rightDeptt);}//_______////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//求树的高度printf("Tree Depth:%d\n",BinaryTreeDepth(root));}intmain(){test01();return0;}

3.6 查找指定数据的节点

思路：

判断根节点；然后对节点存储的数据进行匹配，符合就返回该节点，反之对左子树、右子树进行遍历匹配。要注意的是，一旦左子树匹配成功，无需再对右子树进行遍历。

//Tree.c文件#include"Tree.h"// ⼆叉树查找值为x的结点 BTNode*BinaryTreeFind(BTNode* root, BTDataType x){if(root ==NULL){returnNULL;}//进行匹配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;}returnNULL;}//______////test.c文件#include"Tree.h"voidtest01(){//根节点--创建二叉树 BTNode* root =createTree();//查找if(BinaryTreeFind(root,'G')){printf("找到了！");}elseprintf("不存在！");}intmain(){test01();return0;}

3.7 层序遍历

–利用队列结构实现。

思路： 借队列–>根节点数据入队列，循环判断队列是否为空，不为空就取队头节点，然会将节点的左右孩子入队列。（循环进行）

要用到队列结构，那么先将前面实现的头文件、源文件添加到项目中，并包含上头文件。

在队列的头文件中，将存储数据的变量类型命名int改为为二叉树节点类型，事先声明。

typedef struct BinartNode* QDataType;

// 层序遍历---借助数据结构：队列voidLevelOrder(BTNode* root){ Queue q;QueueInit(&q);//将根节点入队，使队不为空QueuePush(&q, root);//判断队列空/非空while(!QueueEmpty(&q)){//取队头，打印队头 BTNode* top =QueueFront(&q);//接收printf("%c ", top->data);QueuePop(&q);//队头节点不为空的孩子节点入队列if(top->left)QueuePush(&q, top->left);if(top->right)QueuePush(&q, top->right);}QueueDesTroy(&q);}

3.8 判断是否为完全二叉树

–完全二叉树：除最后一层以外其它层节点个数全部达到最大，且节点全是从左到右依次排列。

思路：
先将树的根节点入队，使队不为空。
然后循环的进行取队头、出队头、将头节点的子节点入队（含空），直到取出的节点为空，跳出。
此时，对队列剩余的内容再进行取队头、出队头，判断是否有不为空的节点。

// 判断⼆叉树是否是完全⼆叉树 bool BinaryTreeComplete(BTNode* root){ Queue q;QueueInit(&q);//头节点入队列QueuePush(&q, root);//1次判断队列while(!QueueEmpty(&q)){//取队头，出队头 BTNode* top =QueueFront(&q);QueuePop(&q);if(top ==NULL){//top取到空就直接出队列break;}//将队头节点的左右孩子入队列QueuePush(&q, top->left);QueuePush(&q, top->right);}//2次判断//队列不为空，继续取队列中的队头while(!QueueEmpty(&q)){ BTNode* top =QueueFront(&q);QueuePop(&q);if(top !=NULL){//不是完全二叉树QueueDesTroy(&q);return false;}}QueueDesTroy(&q);return true;}

总结

链式二叉树是递归思维的完美体现。在这棵自我相似的树中，每个节点都遵循相同的结构规则。通过前序、中序、后序三种递归遍历，我们能用简洁代码探索整棵树；通过节点统计、深度计算等操作，我们学会将复杂问题分解为相似子问题。掌握链式二叉树，不仅是学习数据结构，更是培养递归思维的关键一步，为理解更复杂的树形结构奠定基础。

原码获取：gitee_本篇链式二叉树全部原码实现

回顾：
【数据结构】《自此，每一个想考我堆排序（Top-k问题）的面试官，下场都很尴尬【附完整代码实现】》