跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客GitHub 精选镜像工具UI配色美学隐私政策关于联系
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C算法

数据结构：二叉树基础概念与链式存储实现

本文详细讲解了二叉树的数据结构定义、基本术语及性质，重点阐述了链式存储的实现方式。内容包括二叉树的创建、前中后序遍历、层序遍历算法，以及节点计数、高度计算、查找节点和判断完全二叉树等核心功能的代码实现。通过完整的 C 语言代码示例，展示了如何利用队列辅助层序遍历及完全二叉树判定，适合希望深入理解树形结构及其操作的开发者参考。

MongoKing发布于 2026/3/21更新于 2026/6/1522 浏览
数据结构：二叉树基础概念与链式存储实现

数据结构：二叉树基础概念与链式存储实现

一、树的基础概念

1. 树的定义

树是一种非线性数据结构，由 n（n>=0）个有限结点组成一个具有层次关系的集合。有一个特殊的结点称为根结点，它没有前驱结点。除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti 又是一棵结构与树类似的子树。

2. 常见术语

  • 结点的度：一个结点含有的子树的个数。
  • 叶结点：度为 0 的结点。
  • 双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。
  • 树的高度：树中结点的最大层次。

树的结构示意图

二、二叉树详解

1. 什么是二叉树

二叉树是树的一种特殊形式，其树的度最大为 2。也就是说，一个结点最多有两个分叉。由于普通树结构复杂，实际应用中最常用的是二叉树。

二叉树由一个根结点加上两棵别称为左子树和右子树的二叉树组成，且子树有左右之分，次序不能颠倒，因此二叉树是有序树。

二叉树组成

2. 特殊的二叉树

  • 满二叉树：每一层的结点数都达到最大值。如果层数为 K，结点总数是 2^K - 1。
  • 完全二叉树：对于深度为 K 的有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。

注意：满二叉树是一种特殊的完全二叉树。完全二叉树的编号是连续的，中间断开则不是。

满二叉树与完全二叉树

3. 顺序存储与性质

对于完全二叉树，我们可以用数组进行存储，下标对应编号。逻辑上是树，物理上是数组。

重要性质：

  1. 第 i 层最多有 2^(i-1) 个结点。
  2. 深度为 h 的二叉树最大结点数为 2^h - 1。
  3. 叶子结点数 n0 = 度为 2 的结点数 n2 + 1。
  4. 若父亲在数组中下标为 i，则左孩子为 2i+1，右孩子为 2i+2；孩子下标为 i，父亲为 (i-1)/2。

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

非完全二叉树不适合用数组存储，否则空间浪费严重。我们通常采用链式存储，每个结点包含数据域和左右指针域。

1. 节点定义

我们需要定义一个二叉树结构体，包含数据类型、左孩子指针和右孩子指针。为了方便后续修改类型，使用 重定义数据类型。

typedef
// BTNode.h
typedef char BTDataType;

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

2. 构建二叉树

通过前序遍历的数组来构建二叉树是一个经典方法。遇到 '#' 表示空结点。

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

3. 遍历操作

遍历是二叉树的核心操作，主要有前序、中序、后序和层序四种。

前序遍历：根 -> 左 -> 右

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

层序遍历：借助队列实现，一层一层地访问。

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

4. 其他常用功能

除了遍历，我们还需要计算节点个数、高度、查找特定值以及判断是否为完全二叉树。

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

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

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

int BinaryTreeHight(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return fmax(BinaryTreeHight(root->left), BinaryTreeHight(root->right)) + 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;
}

四、完整代码示例

为了便于理解，这里整理了完整的头文件与源文件结构。请确保所有文件在同一目录下编译运行。

Queue.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

typedef struct QListNode {
    QDataType data;
    struct QListNode* next;
} QNode;

typedef struct Queue {
    QNode* front;
    QNode* tail;
    int size;
} Queue;

void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"

void QueueInit(Queue* q) {
    assert(q);
    q->front = NULL;
    q->tail = NULL;
    q->size = 0;
}

void QueuePush(Queue* q, QDataType data) {
    assert(q);
    QNode* tmp = (QNode*)malloc(sizeof(QNode));
    if (tmp == NULL) {
        perror("malloc failed");
        return;
    }
    tmp->data = data;
    tmp->next = NULL;
    if (q->size == 0) {
        q->front = tmp;
        q->tail = tmp;
    } else {
        q->tail->next = tmp;
        q->tail = tmp;
    }
    q->size++;
}

void QueuePop(Queue* q) {
    assert(q);
    assert(q->size > 0);
    if (q->size == 1) {
        free(q->front);
        q->front = NULL;
        q->tail = NULL;
    } else {
        QNode* del = q->front;
        q->front = q->front->next;
        free(del);
    }
    q->size--;
}

QDataType QueueFront(Queue* q) {
    assert(q);
    assert(q->size > 0);
    return q->front->data;
}

QDataType QueueBack(Queue* q) {
    assert(q);
    assert(q->size > 0);
    return q->tail->data;
}

int QueueSize(Queue* q) {
    assert(q);
    return q->size;
}

int QueueEmpty(Queue* q) {
    assert(q);
    return q->size == 0;
}

void QueueDestroy(Queue* q) {
    assert(q);
    QNode* cur = q->front;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->front = q->tail = NULL;
    q->size = 0;
}

BTNode.h

#pragma once
#include "Queue.h"

typedef char BTDataType;

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

BTNode* BinaryTreeCreate(BTDataType* ch, int* pi);
void BinaryTreePrevOrder(BTNode* root);
void BinaryTreeInOrder(BTNode* root);
void BinaryTreePostOrder(BTNode* root);
int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeHight(BTNode* root);
void BinaryTreeDestory(BTNode** root);
int BinaryTreeLevelKSize(BTNode* root, int k);
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
int BinaryTreeComplete(BTNode* root);
void BinaryTreeLevelOrder(BTNode* root);

BTNode.c

#include "BTNode.h"

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

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

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

void BinaryTreeDestory(BTNode** root) {
    if (*root == NULL) {
        return;
    }
    BinaryTreeDestory(&(*root)->left);
    BinaryTreeDestory(&(*root)->right);
    free(*root);
    *root = NULL;
}

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

int BinaryTreeHight(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return fmax(BinaryTreeHight(root->left), BinaryTreeHight(root->right)) + 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);
}

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

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);
    } else {
        printf("未找到\n");
    }

    if (BinaryTreeComplete(T)) {
        printf("是完全二叉树\n");
    } else {
        printf("不是完全二叉树\n");
    }

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

    BinaryTreeDestory(&T);
    return 0;
}

以上就是二叉树的基础理论与 C 语言实现的完整讲解。掌握这些内容后，建议多动手编写代码，加深理解。

目录

  1. 数据结构：二叉树基础概念与链式存储实现
  2. 一、树的基础概念
  3. 1. 树的定义
  4. 2. 常见术语
  5. 二、二叉树详解
  6. 1. 什么是二叉树
  7. 2. 特殊的二叉树
  8. 3. 顺序存储与性质
  9. 三、二叉树的链式存储实现
  10. 1. 节点定义
  11. 2. 构建二叉树
  12. 3. 遍历操作
  13. 4. 其他常用功能
  14. 四、完整代码示例
  15. Queue.h
  16. Queue.c
  17. BTNode.h
  18. BTNode.c
  19. Test.c
  • 免费图片AI生成工具免费生成了解详情
  • Magick API 一键接入全球大模型注册送1000万token查看
  • 免费图片视频在线生成30秒，将你的创意变成现实开始设计
  • X/Twitter免费视频下载器免登陆无限额度免费视频解析下载了解详情
  • 100+免费在线小游戏爽一把
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog

更多推荐文章

查看全部
  • Transformer 20 个常见面试问题解析：从基础到高级
  • AIGC 产品经理转行指南：核心技能与实战项目解析
  • Webhook 核心原理及 Langflow 自动化工作流实践
  • 预训练语言模型与 BERT 实战应用
  • Docker 部署 OpenClaw：Web UI 访问、飞书配对及模型配置
  • VSCode Copilot 登录失败常见原因与解决方案
  • Linux 文件 I/O 全景指南：从 open 到重定向详解
  • Windows 下安装与配置 ZeroClaw 本地机器人
  • macOS 部署安装 IndexTTS2
  • 基于 Openclaw 与 Seed2.0 Skills 构建 AI 漫剧生成工作流
  • Go Map 底层原理深度解析
  • VSCode 配置 DeepSeek 模型接入 Copilot
  • OFA 图文蕴含模型部署：AI 绘画提示词与图像匹配度评分
  • Qwen3 与 Qwen Agent 智能体开发实战：接入 MCP 工具
  • Java 面试核心：哈希冲突与 equals/hashCode 详解
  • Stable Diffusion 显存优化方案与自动释放扩展使用指南
  • 小米智能家居 Miloco 分离式部署指南
  • 鸿蒙应用开发常用资源与工具指南
  • RoboBrain2.0 具身大脑模型复现：统一感知、推理和规划能力
  • 基于 SSM Web 的教师业绩管理系统设计与实现

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown转HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online