数据结构初阶：二叉树的链式存储与实现

一、二叉树的链式结构

顺序存储虽然直观，但在处理稀疏树或动态增长场景时存在空间浪费。链式存储通过指针将节点连接起来，更加灵活。二叉树的链式结构主要分为二叉链（含左右指针）和三叉链（含父指针），本教程重点讲解最常用的二叉链。

// 定义二叉树节点
typedef char Elemtype;
typedef struct BinaryTree {
    Elemtype data;
    struct BinaryTree* leftChild;
    struct BinaryTree* rightChild;
} BTNode;

每个节点包含数据域和两个指针域，分别指向左子树和右子树的根节点地址。这种结构天然适合递归操作。

二、二叉树的创建

在掌握基本性质后，我们手动构建一棵二叉树来演示节点链接。相比复杂的增删查改逻辑，手动初始化有助于理解树形结构。

1. 节点创建辅助函数

创建节点需分配内存并初始化指针，防止野指针。

BTNode* BuyNode(Elemtype data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL) {
        perror("create new node fail!");
        return NULL;
    }
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return newNode;
}

注意：务必检查 malloc 返回值，并在返回前确保指针已初始化。

2. 手动链接节点

通过调用 BuyNode 生成节点，再手动设置 leftChild 和 rightChild 指针。

BTNode* createNewBT() {
    // 创建节点 A-I, O
    BTNode* NodeA = BuyNode('A');
    BTNode* NodeB = BuyNode('B');
    BTNode* NodeC = BuyNode('C');
    BTNode* NodeD = BuyNode('D');
    BTNode* NodeE = BuyNode('E');
    BTNode* NodeF = BuyNode('F');
    BTNode* NodeG = BuyNode('G');
    BTNode* NodeH = BuyNode('H');
    BTNode* NodeI = BuyNode('I');
    BTNode* NodeO = BuyNode('O');

    // 建立连接关系
    NodeA->leftChild = NodeB;   NodeA->rightChild = NodeC;
    NodeB->leftChild = NodeD;   NodeB->rightChild = NodeE;
    NodeD->leftChild = NodeH;   
    NodeC->leftChild = NodeF;   NodeF->leftChild = NodeI;
    NodeH->leftChild = NodeO;

    return NodeA; // 返回根节点
}

这棵树的结构是：根为 A，左子树 B，右子树 C... 以此类推。实际开发中，通常通过数组序列化字符串（如 "ABD#H#O##CE#F#I##"）来自动构建，但手动构建更利于调试。

三、链式二叉树的基本操作

1. 三种深度优先遍历

前序遍历 (根 -> 左 -> 右)

访问根节点后，先递归左子树，再递归右子树。

void PreOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->leftChild);
    PreOrder(root->rightChild);
}

中序遍历 (左 -> 根 -> 右)

先遍历左子树，访问根节点，最后遍历右子树。

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

后序遍历 (左 -> 右 -> 根)

左右子树均遍历完后，才访问根节点。常用于释放内存。

void LastOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    LastOrder(root->leftChild);
    LastOrder(root->rightChild);
    printf("%c ", root->data);
}

2. 统计与查找

计算总结点个数

利用递归思想：总数 = 左子树节点数 + 右子树节点数 + 1(根节点)。

int BinaryTreeSize_of_Node(BTNode* root) {
    if (root == NULL) return 0;
    return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}

计算叶子节点个数

叶子节点定义为左右孩子均为空。若当前节点满足条件则计数 1，否则累加左右子树的叶子数。

int BinaryTreesize_of_Leaf(BTNode* root) {
    if (root == NULL) return 0;
    if (root->leftChild == NULL && root->rightChild == NULL) return 1;
    return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}

计算第 k 层节点个数

递归时 k 减 1，当 k=1 时说明到达目标层，返回 1。

int BinaryTreeSize_of_K(BTNode* root, int k) {
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}

计算二叉树深度

深度取决于左右子树深度的最大值加 1。

int BinaryTreeSize_of_Depth(BTNode* root) {
    if (root == NULL) return 0;
    int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
    int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

查找元素

遍历整棵树，找到目标值即停止。

void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
    if (root == NULL) return;
    if (root->data == val) {
        printf("找到了!\n");
        return;
    }
    BinaryTreeSearch_of_val(root->leftChild, val);
    BinaryTreeSearch_of_val(root->rightChild, val);
}

3. 层序遍历与完全二叉树判断

层序遍历需要借助队列（先进先出）。思路是：根入队 -> 出队打印 -> 左右孩子入队 -> 循环直到队空。

void LevelOrder(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        printf("%c ", top->data);
        Pop_Queue(pQueue);
        if (top->leftChild) Push_Queue(pQueue, top->leftChild);
        if (top->rightChild) Push_Queue(pQueue, top->rightChild);
    }
    DestroyQueue(pQueue);
}

判断完全二叉树同样基于层序遍历。遇到第一个空节点后，后续所有节点必须为空才是完全二叉树。

bool IsBinaryTree_of_Complete(BTNode* root) {
    Queue q;
    Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        QElemtype top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top == NULL) break;
        Push_Queue(pQueue, top->leftChild);
        Push_Queue(pQueue, top->rightChild);
    }
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top != NULL) {
            DestroyQueue(pQueue);
            return false;
        }
    }
    DestroyQueue(pQueue);
    return true;
}

四、完整代码整合

以下代码整合了二叉树核心逻辑与队列实现。实际项目中建议将队列功能封装为独立头文件引入。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"

typedef char Elemtype;

typedef struct BinaryTree {
    Elemtype data;
    struct BinaryTree* leftChild;
    struct BinaryTree* rightChild;
} BTNode;

BTNode* BuyNode(Elemtype data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL) { perror("create new node fail!"); return NULL; }
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return newNode;
}

BTNode* createNewBT() {
    BTNode* NodeA = BuyNode('A');
    BTNode* NodeB = BuyNode('B');
    BTNode* NodeC = BuyNode('C');
    BTNode* NodeD = BuyNode('D');
    BTNode* NodeE = BuyNode('E');
    BTNode* NodeF = BuyNode('F');
    BTNode* NodeG = BuyNode('G');
    BTNode* NodeH = BuyNode('H');
    BTNode* NodeI = BuyNode('I');
    BTNode* NodeO = BuyNode('O');
    NodeA->leftChild = NodeB;   NodeA->rightChild = NodeC;
    NodeB->leftChild = NodeD;   NodeB->rightChild = NodeE;
    NodeD->leftChild = NodeH;   
    NodeC->leftChild = NodeF;   NodeF->leftChild = NodeI;
    NodeH->leftChild = NodeO;
    return NodeA;
}

void PreOrder(BTNode* root) {
    if (root == NULL) { printf("NULL "); return; }
    printf("%c ", root->data); PreOrder(root->leftChild); PreOrder(root->rightChild);
}

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

void LastOrder(BTNode* root) {
    if (root == NULL) { printf("NULL "); return; }
    LastOrder(root->leftChild); LastOrder(root->rightChild); printf("%c ", root->data);
}

int BinaryTreeSize_of_Node(BTNode* root) {
    if (root == NULL) return 0;
    return 1 + BinaryTreeSize_of_Node(root->leftChild) + BinaryTreeSize_of_Node(root->rightChild);
}

int BinaryTreesize_of_Leaf(BTNode* root) {
    if (root == NULL) return 0;
    if (root->leftChild == NULL && root->rightChild == NULL) return 1;
    return BinaryTreesize_of_Leaf(root->leftChild) + BinaryTreesize_of_Leaf(root->rightChild);
}

int BinaryTreeSize_of_K(BTNode* root, int k) {
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return BinaryTreeSize_of_K(root->leftChild, k - 1) + BinaryTreeSize_of_K(root->rightChild, k - 1);
}

int BinaryTreeSize_of_Depth(BTNode* root) {
    if (root == NULL) return 0;
    int leftDepth = BinaryTreeSize_of_Depth(root->leftChild);
    int rightDepth = BinaryTreeSize_of_Depth(root->rightChild);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

void BinaryTreeSearch_of_val(BTNode* root, Elemtype val) {
    if (root == NULL) return;
    if (root->data == val) { printf("找到了!\n"); return; }
    BinaryTreeSearch_of_val(root->leftChild, val);
    BinaryTreeSearch_of_val(root->rightChild, val);
}

void LevelOrder(BTNode* root) {
    Queue q; Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        printf("%c ", top->data);
        Pop_Queue(pQueue);
        if (top->leftChild) Push_Queue(pQueue, top->leftChild);
        if (top->rightChild) Push_Queue(pQueue, top->rightChild);
    }
    DestroyQueue(pQueue);
}

bool IsBinaryTree_of_Complete(BTNode* root) {
    Queue q; Queue* pQueue = &q;
    InitQueue(pQueue);
    Push_Queue(pQueue, root);
    while (!isEmpty(pQueue)) {
        QElemtype top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top == NULL) break;
        Push_Queue(pQueue, top->leftChild);
        Push_Queue(pQueue, top->rightChild);
    }
    while (!isEmpty(pQueue)) {
        BTNode* top = GetElemFront(pQueue);
        Pop_Queue(pQueue);
        if (top != NULL) { DestroyQueue(pQueue); return false; }
    }
    DestroyQueue(pQueue);
    return true;
}

int main() {
    BTNode* NodeA = createNewBT();
    printf("前序遍历:"); PreOrder(NodeA); printf("\n");
    printf("中序遍历:"); InOrder(NodeA); printf("\n");
    printf("后序遍历:"); LastOrder(NodeA); printf("\n");
    printf("总结点数：%d\n", BinaryTreeSize_of_Node(NodeA));
    printf("叶子节点数：%d\n", BinaryTreesize_of_Leaf(NodeA));
    printf("第4层节点数：%d\n", BinaryTreeSize_of_K(NodeA, 4));
    printf("深度：%d\n", BinaryTreeSize_of_Depth(NodeA));
    printf("层序遍历:"); LevelOrder(NodeA); printf("\n");
    printf(IsBinaryTree_of_Complete(NodeA) ? "是完全二叉树\n" : "不是完全二叉树\n");
    return 0;
}

以上便是二叉树链式存储的核心实现。理解递归终止条件和指针操作是关键，多动手调试能加深印象。