链式二叉树详解：递归遍历与核心接口实现

2.1 前序遍历（根左右）

前序遍历即先访问当前节点，再递归遍历左子树，最后递归遍历右子树。

实现思路： 遇到空节点直接返回；否则打印当前数据，然后依次递归调用左、右子树。

void PreOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);      // 1. 访问根
    PreOrder(root->left);           // 2. 递归左
    PreOrder(root->right);          // 3. 递归右
}

2.2 中序遍历（左根右）

中序遍历的顺序是先左子树，再根节点，最后右子树。对于二叉搜索树，中序遍历能得到有序序列。

void InOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    InOrder(root->left);            // 1. 递归左
    printf("%c ", root->data);      // 2. 访问根
    InOrder(root->right);           // 3. 递归右
}

2.3 后序遍历（左右根）

后序遍历最后访问根节点，常用于释放树内存或计算目录大小等场景。

void PostOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);          // 1. 递归左
    PostOrder(root->right);         // 2. 递归右
    printf("%c ", root->data);      // 3. 访问根
}

三、其他常用接口实现

除了遍历，统计节点数、求高度、查找节点等操作同样依赖递归思想。

3.1 构造二叉树

为了方便测试，我们需要手动构建一棵特定的树结构。

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;
    }
    // 当前节点 + 左子树节点 + 右子树节点
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

错误方法：全局变量

尝试使用全局变量 size 计数。虽然能算出结果，但破坏了函数的纯函数特性，多次调用时状态无法重置，极易引发 Bug。

低效方法：传参

通过指针参数传递计数器。虽然避免了全局变量污染，但改变了接口签名，每次调用前需手动初始化，不够优雅。

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

3.4 求第 k 层节点的个数

当 k=1 时，说明到达目标层，返回 1；否则递归向下查找 k-1 层。

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 求树的高度/深度

树的高度取决于左右子树中较高的那一个，再加上根节点这一层。

int BinaryTreeDepth(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = BinaryTreeDepth(root->left);
    int rightDepth = BinaryTreeDepth(root->right);
    // 取较大值并加 1
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

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;
    }
    // 左子树没找到再去右子树找
    return BinaryTreeFind(root->right, x);
}

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

总结

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