跳到主要内容
数据结构：二叉树基础概念与链式存储实现 | 极客日志
C 算法
数据结构：二叉树基础概念与链式存储实现 本文详细讲解了二叉树的数据结构定义、基本术语及性质，重点阐述了链式存储的实现方式。内容包括二叉树的创建、前中后序遍历、层序遍历算法，以及节点计数、高度计算、查找节点和判断完全二叉树等核心功能的代码实现。通过完整的 C 语言代码示例，展示了如何利用队列辅助层序遍历及完全二叉树判定，适合希望深入理解树形结构及其操作的开发者参考。
MongoKing 发布于 2026/3/21 更新于 2026/4/25 数据结构：二叉树基础概念与链式存储实现
一、树的基础概念
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. 顺序存储与性质
对于完全二叉树，我们可以用数组进行存储，下标对应编号。逻辑上是树，物理上是数组。
重要性质：
第 i 层最多有 2^(i-1) 个结点。
深度为 h 的二叉树最大结点数为 2^h - 1。
叶子结点数 n0 = 度为 2 的结点数 n2 + 1。
若父亲在数组中下标为 i，则左孩子为 2i+1，右孩子为 2 i+2；孩子下标为 i，父亲为 (i-1)/2。
三、二叉树的链式存储实现
非完全二叉树不适合用数组存储，否则空间浪费严重。我们通常采用链式存储，每个结点包含数据域和左右指针域。
1. 节点定义
我们需要定义一个二叉树结构体，包含数据类型、左孩子指针和右孩子指针。为了方便后续修改类型，使用
typedef
typedef char BTDataType;
typedef struct BinaryTreeNode {struct BinaryTreeNode * left ;struct BinaryTreeNode * right ;
2. 构建二叉树 通过前序遍历的数组来构建二叉树是一个经典方法。遇到 '#' 表示空结点。
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. 其他常用功能 除了遍历，我们还需要计算节点个数、高度、查找特定值以及判断是否为完全二叉树。
int BinaryTreeSize (BTNode* root) {
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1 ;
}
int BinaryTreeHight (BTNode* root) {
if (root == NULL ) {
return 0 ;
}
return fmax(BinaryTreeHight(root->left), BinaryTreeHight(root->right)) + 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 ;
}
四、完整代码示例 为了便于理解，这里整理了完整的头文件与源文件结构。请确保所有文件在同一目录下编译运行。
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 {struct QListNode * next ;typedef struct Queue {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 {struct BinaryTreeNode * left ;struct BinaryTreeNode * right ;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 语言实现的完整讲解。掌握这些内容后，建议多动手编写代码，加深理解。
相关免费在线工具 加密/解密文本 使用加密算法（如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
