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

一、二叉树的链式结构

有了顺序存储结构，自然也会想到链式存储。在二叉树的讲解中，我们提到过二叉链和三叉链，现阶段主要关注二叉链。

// 链式二叉树的节点
typedef struct BinaryTree {
    Elemtype data;
    struct BinaryTree* leftChild;
    struct BinaryTree* rightChild;
} BTNode;

每个节点包含数据域和指针域。数据域存储当前值，指针域分别指向左子树和右子树的地址，便于直接访问子节点。

二、二叉树的创建

为了快速上手并理解基本性质，我们先手动创建一棵二叉树，暂不涉及复杂的增删查改操作。

2.1、创建二叉树节点

与链表节点类似，分配内存并初始化指针。

// 创建新节点
BTNode* BuyNode(Elemtype data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL) {
        perror("create new node fail!\n");
    }
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return newNode;
}

注意返回新节点的指针，否则后续无法访问。

2.2、二叉树节点的链接

通过指针将根节点与左右子树连接起来。

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

构建出的树结构如下所示：

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

主要涉及遍历、统计及查找等操作。

3.1、前序遍历

访问顺序：根 -> 左 -> 右。

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

递归终止条件是节点为空。以叶子节点 O 为例，其左右孩子均为 NULL，递归返回后打印自身，整棵树遵循'根左右'原则执行。

3.2、中序遍历

访问顺序：左 -> 根 -> 右。

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

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

3.3、后序遍历

访问顺序：左 -> 右 -> 根。

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

左右子树全部遍历完毕后，才访问根节点。

3.4、计算二叉树的总结点个数

采用递归方式，统计左右子树节点数之和。

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

3.5、计算二叉树的叶子结点个数

叶子节点定义为左右孩子均为空的节点。

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

3.6、计算第 k 层节点个数

递归统计左子树第 k-1 层与右子树第 k-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);
}

当 k=1 时，无论输入还是递归到达，该层只有一个根节点。

3.7、计算二叉树的深度

比较左右子树的最大深度，加 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);
}

3.8、查找元素

遍历整棵树，匹配目标值。

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

借助队列实现，按层级从左到右访问。

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

3.10、判断是否为完全二叉树

利用层序遍历，遇到空节点后，后续节点必须全为空。

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

3.11、外部代码的引入

需将队列相关代码（如 Queue.h）引入项目。注意类型定义的一致性，队列元素类型应调整为 struct BinaryTree*。

四、综合代码

整合上述功能进行测试。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.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!\n");
    }
    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->rightChild) + BinaryTreesize_of_Leaf(root->leftChild);
}

int BinaryTreeSize_of_K(BTNode* root, int k) {
    if (root == NULL) { return 0; }
    if (k == 1) { return 1; }
    else { return BinaryTreeSize_of_K(root->rightChild, k - 1) + BinaryTreeSize_of_K(root->leftChild, 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\n");
    printf("中序遍历:"); InOrder(NodeA); printf("\n\n");
    printf("后序遍历:"); LastOrder(NodeA); printf("\n\n");
    int size_of_totalNode = BinaryTreeSize_of_Node(NodeA);
    printf("当前二叉树的总结点个数为：%d", size_of_totalNode); printf("\n\n");
    int size_of_LeafNode = BinaryTreesize_of_Leaf(NodeA);
    printf("当前二叉树的叶子结点个数为：%d", size_of_LeafNode); printf("\n\n");
    int size_of_KNode = BinaryTreeSize_of_K(NodeA, 4);
    printf("当前二叉树的第 4 层的结点个数为：%d", size_of_KNode); printf("\n\n");
    int size_of_Depth = BinaryTreeSize_of_Depth(NodeA);
    printf("当前二叉树的层数为：%d", size_of_Depth); printf("\n\n");
    BinaryTreeSearch_of_val(NodeA, 'I');
    printf("层序遍历的结果为："); LevelOrder(NodeA); printf("\n\n");
    if (IsBinaryTree_of_Complete(NodeA)) {
        printf("一棵完全二叉树");
    } else {
        printf("这不是完全二叉树...\n");
    }
    return 0;
}

对应的队列实现文件 Queue.h 需包含基础入队出队逻辑，注意类型重定义。

运行结果验证了各功能的正确性，整体结构清晰，便于理解二叉树的核心操作逻辑。