数据结构：二叉树基础与 C 语言实现

三、二叉树的链式存储与实现

1. 链式存储思路

非完全二叉树不适合用数组存储，否则会造成大量空间浪费。我们通常使用链式存储，即创建链表，使每个结点由三个域组成：数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在结点的地址。

2. 代码实现

本文以创建一个 char 类型的二叉树为例。为了便于类型修改，我们使用 typedef 重定义数据类型。

（1）头文件与源文件规划

建议将函数声明放在头文件中，函数定义放在源文件中，测试代码单独编写。

（2）定义二叉树结构

// BTNode.h
#pragma once
#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

typedef char BTDataType;

typedef struct BinaryTreeNode {
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

（3）构建二叉树

通过前序遍历的数组来构建二叉树，例如 "ABD##E#H##CF##G##"，其中 # 代表空节点。

// BTNode.c
BTNode* BinaryTreeCreate(BTDataType* ch, int* pi) {
    if (ch[*pi] == '#') {
        return NULL;
    }
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = ch[(*pi)++];
    newnode->left = BinaryTreeCreate(ch, pi);
    (*pi)++;
    newnode->right = BinaryTreeCreate(ch, pi);
    return newnode;
}

（4）二叉树遍历

遍历主要有四种方式：前序、中序、后序和层序。前三者基于递归，层序基于队列。

前序遍历：先根，再左，最后右。

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

中序遍历：先左，再根，最后右。

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

后序遍历：先左，再右，最后根。

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

（5）层序遍历

层序遍历需要借助队列。每次取出队头元素，将其左右孩子入队，直到队列为空。

void BinaryTreeLevelOrder(BTNode* root) {
    Queue Q;
    QueueInit(&Q);
    if (root) {
        QueuePush(&Q, root);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* node = QueueFront(&Q);
        printf("%c ", node->data);
        QueuePop(&Q);
        if (node->left) {
            QueuePush(&Q, node->left);
        }
        if (node->right) {
            QueuePush(&Q, node->right);
        }
    }
    QueueDestroy(&Q);
}

（6）节点统计与高度计算

节点个数：递归计算左右子树节点数加 1。

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

叶子节点个数：左右子树均为空的节点。

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

树的高度：左右子树高度的最大值加 1。

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

（7）其他功能实现

第 k 层节点个数：递归减少 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);
}

查找值为 x 的节点：递归查找，找到直接返回地址。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == x) {
        return root;
    }
    BTNode* ret1 = BinaryTreeFind(root->left, x);
    if (ret1) {
        return ret1;
    }
    BTNode* ret2 = BinaryTreeFind(root->right, x);
    if (ret2) {
        return ret2;
    }
    return NULL;
}

判断是否是完全二叉树：利用层序遍历，遇到空节点后不应再有非空节点。

int BinaryTreeComplete(BTNode* root) {
    Queue Q;
    QueueInit(&Q);
    if (root) {
        QueuePush(&Q, root);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* node = QueueFront(&Q);
        QueuePop(&Q);
        if (node == NULL) {
            break;
        }
        QueuePush(&Q, node->left);
        QueuePush(&Q, node->right);
    }
    while (!QueueEmpty(&Q)) {
        BTNode* node = QueueFront(&Q);
        QueuePop(&Q);
        if (node != NULL) {
            QueueDestroy(&Q);
            return 0;
        }
    }
    QueueDestroy(&Q);
    return 1;
}

（8）完整代码示例

包含队列实现的完整代码可参考以下文件结构：

• Queue.h, Queue.c: 队列操作
• BTNode.h, BTNode.c: 二叉树操作
• Test.c: 测试主函数

// Test.c
#include "BTNode.h"

int main() {
    char ch[100] = "ABD##E#H##CF##G##";
    int i = 0;
    BTNode* T = BinaryTreeCreate(ch, &i);

    printf("节点个数：%d\n", BinaryTreeSize(T));
    printf("叶子节点个数：%d\n", BinaryTreeLeafSize(T));
    printf("高度：%d\n", BinaryTreeHight(T));
    printf("第 3 层节点个数：%d\n", BinaryTreeLevelKSize(T, 3));

    BTNode* ret = BinaryTreeFind(T, 'G');
    if (ret) {
        printf("找到 G: %c\n", ret->data);
    }

    printf("是否完全二叉树：%s\n", BinaryTreeComplete(T) ? "是" : "否");

    printf("前序：");
    BinaryTreePrevOrder(T);
    printf("\n");
    printf("中序：");
    BinaryTreeInOrder(T);
    printf("\n");
    printf("后序：");
    BinaryTreePostOrder(T);
    printf("\n");
    printf("层序：");
    BinaryTreeLevelOrder(T);
    printf("\n");

    // 销毁树
    // 此处需补充 BinaryTreeDestory 调用逻辑
    return 0;
}

四、总结

本文详细讲解了二叉树的定义、性质及 C 语言实现。重点涵盖了递归遍历、层序遍历以及各类统计功能的代码实现。理解这些基础操作对于后续学习更复杂的树形结构至关重要。