链式二叉树的递归遍历与常用接口

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

这个接口最适合拿来练递归返回值。做法不复杂：当前节点算 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；否则就往下一层递归。

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

层序遍历不是递归，而是队列的活。它按层往下扫，适合做广度优先遍历。

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

总结

链式二叉树最有价值的地方，不是'树长什么样'，而是它把递归的边界和返回值都暴露得很清楚。前序、中序、后序这几种遍历，基本就是递归模板的几种变体；节点数、高度、查找、层序遍历这些接口，则把'把大问题拆成同类子问题'这件事做得很直接。二叉树学明白了，后面再看更复杂的树结构，思路会顺很多。