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

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

// 前序遍历---根左右
void PreOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

测试代码示例：

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

void test01() {
    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;
    nodeC->left = nodeE;
    nodeC->right = nodeF;
    
    PreOrder(nodeA);
}

int main() {
    test01();
    return 0;
}

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

遍历二叉树时，只要节点不为空，个数就 +1，为空则返回。树的有效节点个数 = 左子树有效节点个数 + 右子树有效节点个数。

正确方法

利用返回值累加，每次递归返回当前子树的节点数。

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

// 树的有效节点个数
int BinaryTreeSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

错误方法对比

• 全局变量/静态修饰：多次调用函数时，变量会继承上次调用的值，导致统计错误。
• 传参：虽然避免了累加，但破坏了接口一致性，且每次使用前需手动重置计数变量，使用不便。

3.3 二叉树叶子节点个数

某节点的左、右孩子节点均为 NULL 时，就叫叶子节点。总的叶子节点个数 = 左子树叶子节点数 + 右子树叶子节点数。

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

// 二叉树的叶子节点个数
int BinaryTreeLeafSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    // 叶子节点条件，左右子节点均为 NULL
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

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

层序遍历属于广度优先搜索，利用队列结构实现。借队列：根节点数据入队列，循环判断队列是否为空，不为空就取队头节点，然后将节点的左右孩子入队列。

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

// 层序遍历---借助数据结构：队列
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 判断是否为完全二叉树

完全二叉树：除最后一层以外其它层节点个数全部达到最大，且节点全是从左到右依次排列。

思路：先将树的根节点入队，循环取队头、出队头、将头节点的子节点入队（含空），直到取出的节点为空，跳出。此时，对队列剩余的内容再进行取队头、出队头，判断是否有不为空的节点。

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

// 判断二叉树是否是完全二叉树
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;
}

总结

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