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

2.2 中序遍历

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

void InOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

2.3 后序遍历

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

void PostOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

三、其他核心接口

为了方便演示，我们假设已有一个构建好的二叉树。

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 统计有效节点个数

正确方法： 利用返回值累加。总数 = 1 + 左子树节点数 + 右子树节点数。

int BinaryTreeSize(BTNode* root) {
    if (root == NULL) return 0;
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

错误示例： 使用全局变量或静态变量。递归调用会共享同一份状态，导致多次调用时计数累加错误，且无法重置。

低效示例： 传参修改。虽然可行，但破坏了函数接口的纯粹性，每次调用前需手动初始化计数器。

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

高度为左右子树最大高度加 1。

int BinaryTreeDepth(BTNode* root) {
    if (root == NULL) return 0;
    int leftHeight = BinaryTreeDepth(root->left);
    int rightHeight = BinaryTreeDepth(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

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 层序遍历

层序遍历属于广度优先搜索，通常借助队列实现。将根节点入队，循环取出队头并打印，将其非空的孩子节点依次入队。

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

总结

链式二叉树是理解递归思维的绝佳范例。通过前序、中序、后序遍历，我们可以用简洁的代码探索整棵树；通过节点统计、深度计算等操作，学会将复杂问题分解为相似子问题。掌握这些基础操作，不仅是学习数据结构的关键，更是培养递归思维、应对更复杂树形结构的基础。