数据结构：链式二叉树递归实现与全方位剖析

引言

递归是程序员的必修课，而链式二叉树正是理解递归的绝佳范例。通过实现二叉树的遍历、统计节点、计算深度等操作，我们可以真正掌握递归思维。从函数自调用的困惑到游刃有余的设计，让我们深入这段代码背后的逻辑。

一、介绍链式二叉树

1.1 概念

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

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

链式二叉树的节点由三部分构成：存储数据的变量、指向左孩子节点的指针、指向右孩子节点的指针。

// 定义链式二叉树的结构--节点结构
typedef int BTDataType;
typedef struct BinaryTreeNode {
    BTDataType data; // 存储数据
    struct BinaryTreeNode* left; // 指针指向左孩子节点（左子树）
    struct BinaryTreeNode* 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"

// 前序遍历---根左右
void PreOrder(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"

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;
    PreOrder(nodeA);
}

int main() {
    test01();
    return 0;
}

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"

// 中序遍历---左根右
void InOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    // 根据规则，先前中遍历左子树
    InOrder(root->left);
    // 输出根节点
    printf("%c ", root->data);
    // 最后对右子树进行中序遍历
    InOrder(root->right);
}

//________________////test.c 文件 include "Tree.h"
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;
    InOrder(nodeA);
}

int main() {
    test01();
    return 0;
}

思路：（对一个简单的二叉树）首先也是先看整个二叉树的根节点是否为空，为空直接输出 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"
// 后序遍历--左右根
void PostOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    // 根据规则，先后中遍历左子树
    PostOrder(root->left);
    // 遍历完左子树，对右子树进行后序遍历
    PostOrder(root->right);
    // 最后，打印根节点
    printf("%c ", root->data);
}

//______________////test.c 文件
#include "Tree.h"
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;
    PostOrder(nodeA);
}

int main() {
    test01();
    return 0;
}

思路：（对一个简单 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 + 左子树节点个数 + 右子树的节点个数
int BinaryTreeSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//_____________////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 节点个数
    printf("size:%d\n", BinaryTreeSize(root));
    printf("size:%d\n", BinaryTreeSize(root));
}

int main() {
    test01();
    return 0;
}

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

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

只展示主要代码。

思路：（对一个简单 2 层的二叉树）首先创建变量 size 统计节点个数，全局变量。然后先判断根节点是否为空，为空代表没有有效节点，直接返回 0；不为空，那么根节点算一个有效节点，size++。最后，递归调用函数遍历左子树、右子树。

// Tree.c 文件、#include"Tree.h"
// 树的有效节点个数_方法 1
int size = 0; // 定义全局变量
int BinaryTreeSize(BTNode* root) {
    // 根节点为空，即树为空，直接返回结束
    if (root == NULL) {
        return 0;
    }
    // 根节点不为空，根节点为有效节点，size+1
    size++;
    // 递归调用左子树、右子树
    BinaryTreeSize(root->left);
    BinaryTreeSize(root->right);
    return size;
}

//_____________////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 节点个数
    printf("size:%d\n", BinaryTreeSize(root));
    printf("size:%d\n", BinaryTreeSize(root));
}

int main() {
    test01();
    return 0;
}

错误原因：创建局部变量，每次调用函数，变量都被初始化，无法统计。值得注意的是——>全局变量只被初始化一次，此后对变量的修改都会继承；多次调用函数，变量会继承在上次调用后变量的值。

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

2.3 低效率方法：传参

// Tree.c 文件
#include "Tree.h"
// 树的有效节点个数_方法 2
// 传参
int BinaryTreeSize(BTNode* root, int* psize) {
    // 根节点为空，即树为空，直接返回结束
    if (root == NULL) {
        return 0;
    }
    // 根节点不为空，根节点为有效节点，size+1
    (*psize)++;
    // 递归调用左子树、右子树
    BinaryTreeSize(root->left, psize);
    BinaryTreeSize(root->right, psize);
}

//____________////test.c 文件
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 节点个数
    int treeSize = 0;
    BinaryTreeSize(root, &treeSize);
    printf("size:%d\n", treeSize);
    treeSize = 0;
    BinaryTreeSize(root, &treeSize);
    printf("size:%d\n", treeSize);
}

int main() {
    test01();
    return 0;
}

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

3.3 二叉树叶子节点个数

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

2. 代码

// Tree.c 文件
#include "Tree.h"

// 二叉树的叶子节点个数
// 总的叶子节点个数 = 左子树叶子节点数 + 右子树叶子节点数
int BinaryTreeLeafSize(BTNode* root) {
    // 判断整体的根节点
    if (root == NULL) {
        return 0;
    }
    // 叶子节点条件，左右子节点均为 NULL
    if (root->left == NULL && root->right == NULL) {
        return 1; // 叶子节点数 +1
    }
    // 否则继续遍历子树
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//___________////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 总的叶子节点数
    printf("leaf size:%d\n", BinaryTreeLeafSize(root));
}

int main() {
    test01();
    return 0;
}

3.4 求第 k 层节点的个数

1. 概念

求第 k 层的节点个数，要求是有效的节点。根据参数 k，遍历 1 层就 -1，到 k=1 时代表已经到了第 k 层。第 k 层节点个数 = 左子树第 k 层节点个数 + 右子树第 k 层节点个数。

2. 代码

思路：（对一个简单 2 层的二叉树）首先判断根节点是否为空，为空直接返回结束；否则判断是否为 k 层，是 k 层则返回 1，不是就递推调用函数遍历左右孩子节点（左右子树）。

// Tree.c 文件
#include "Tree.h"

// 求第 k 层节点个数
// 第 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);
}

//__________////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 求第 k 层节点个数
    int k = 0;
    printf("Input level:");
    scanf("%d", &k);
    printf("k level size：%d\n", BinaryTreeLevelKSize(root, k));
}

int main() {
    test01();
    return 0;
}

3.5 求树的高度/深度

1. 概念

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

2. 代码

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

// Tree.c 文件
#include "Tree.h"

// 求树的深度/高度
int BinaryTreeDepth(BTNode* root) {
    // 判断根节点
    if (root == NULL) {
        return 0;
    }
    // 提前保存子树高度
    int leftDepth = BinaryTreeDepth(root->left);
    int rightDepth = BinaryTreeDepth(root->right);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

//_______////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 求树的高度
    printf("Tree Depth:%d\n", BinaryTreeDepth(root));
}

int main() {
    test01();
    return 0;
}

3.6 查找指定数据的节点

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

// Tree.c 文件
#include "Tree.h"

// 二叉树查找值为 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;
}

//______////test.c 文件
#include "Tree.h"
void test01() {
    // 根节点--创建二叉树
    BTNode* root = createTree();
    // 查找
    if (BinaryTreeFind(root, 'G')) {
        printf("找到了！");
    } else
        printf("不存在！");
}

int main() {
    test01();
    return 0;
}

3.7 层序遍历

遍历分类	分类方式
前、中、后序遍历	深度优先
层序遍历	广度优先

利用队列结构实现。

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

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

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

typedef struct BinaryNode* QDataType;

// 层序遍历---借助数据结构：队列
void LevelOrder(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;
}

总结

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