链式二叉树递归实现与遍历详解

思路解析： 首先检查根节点是否为空，若为空直接结束；否则先打印当前数据。接着对左子树进行前序遍历（函数内再次调用自己），完成后对右子树进行同样的操作。这种层层递进的调用栈就是递归的核心。

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

2.3 后序遍历（左右根）

后序遍历将根节点放在最后：先遍历左子树，再遍历右子树，最后访问根节点。

代码实现：

// 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 树的有效节点个数

求节点总数时，如果节点不为空，计数加一，然后累加左右子树的节点数。

正确方法（推荐）：

int BinaryTreeSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    // 总数 = 1 + 左子树节点数 + 右子树节点数
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

避坑指南： 有些初学者喜欢用全局变量或静态变量来计数，这在多次调用函数时会出错，因为变量状态无法重置。传参法虽然可行，但破坏了接口的简洁性。返回值累加是最符合递归语义的做法。

3.3 二叉树叶子节点个数

叶子节点定义为左右孩子均为 NULL 的节点。总叶子数等于左右子树叶子数之和。

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。

int BinaryTreeLevelKSize(BTNode* root, int k) {
    if (root == NULL) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    // 递归遍历左右子树，k 减 1
    return BinaryTreeLevelKSize(root->left, k - 1) + 
           BinaryTreeLevelKSize(root->right, k - 1);
}

3.5 求树的高度/深度

树的高度 = 1 + max(左子树高度，右子树高度)。

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 查找指定数据的节点

匹配根节点数据，若不符则分别在左右子树中查找。注意一旦左子树找到结果，无需再查右子树。

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);
    return rightFind;
}

3.7 层序遍历

层序遍历属于广度优先搜索（BFS），需要借助队列来实现。

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

总结

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