数据结构：链式二叉树的递归实现与核心接口解析

2.2 中序遍历（左根右）

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

思路：首先看整个二叉树的根节点是否为空，为空直接输出 NULL，结束；不为空，对左子树进行中序遍历，再次调用自己，将根节点的左孩子指针传参。遍历完左子树，打印根节点数据。最后对右子树进行中序遍历，也是在函数内再次调用自己，将根节点的右孩子指针传参。

// 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);
}

2.3 后序遍历

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

思路：首先也是先看整个二叉树的根节点是否为空，为空，代表树为空，直接输出 NULL，结束；不为空，对左子树进行中序遍历，在函数内再次调用自己，将根节点的左孩子指针传参。遍历完左子树，再次递归调用函数，将根节点的右孩子指针传参。最后打印根节点数据。

// 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);
}

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

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

3.1 构造二叉树

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

// 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;
    nodeB->right = nodeE;
    nodeC->left = nodeF;
    return nodeA;
}

3.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);
}

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

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

只展示主要代码。思路是创建变量 size 统计节点个数，全局变量。然后先判断根节点是否为空，为空代表没有有效节点，直接返回 0；不为空，那么根节点算一个有效节点，size++。最后，递归调用函数遍历左子树、右子树。

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

// 树的有效节点个数_方法 1
int size = 0; // 定义全局变量
int BinaryTreeSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    size++;
    BinaryTreeSize(root->left);
    BinaryTreeSize(root->right);
    return size;
}

错误原因：创建局部变量，每次调用函数，变量都被初始化，无法统计。值得注意的是——全局变量只被初始化一次，此后对变量的修改都会继承；多次调用函数，变量会继承在上次调用后变量的值。那么对变量进行 static 修饰呢？也不行！因为 static 修饰的全局变量虽然生命周期延长，但在多态或并发场景下依然容易出错，且破坏了函数的纯度和可重入性。

低效率方法：传参

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

// 树的有效节点个数_方法 2
// 传参
int BinaryTreeSize(BTNode* root, int* psize) {
    if (root == NULL) {
        return 0;
    }
    (*psize)++;
    BinaryTreeSize(root->left, psize);
    BinaryTreeSize(root->right, psize);
}

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

3.3 二叉树叶子节点个数

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

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

// 二叉树的叶子节点个数
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);
}

3.4 求第 k 层节点的个数

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

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

// 求第 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);
}

3.5 求树的高度/深度

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

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

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

// 求树的深度/高度
int BinaryTreeDepth(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDeptt = BinaryTreeDepth(root->left);
    int rightDeptt = BinaryTreeDepth(root->right);
    return 1 + (leftDeptt > rightDeptt ? leftDeptt : rightDeptt);
}

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;
}

3.7 层序遍历

层序遍历属于广度优先搜索，利用队列结构实现。

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

要用到队列结构，那么先将前面实现的头文件、源文件添加到项目中，并包含上头文件。在队列的头文件中，将存储数据的变量类型命名为二叉树节点类型，事先声明。

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

总结

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