C语言：二叉树（上）-平芜编程栈

文章目录

1. 树概念及结构
- 1.1 树的核心概念
- 1.3 树的表示
2. 二叉树
- 2.1 二叉树的概念
- 2.2 特殊的二叉树
- - 2.2.1 满二叉树
  - 2.2.2 完全二叉树
- 2.3 二叉树的性质
- 2.4 二叉树的存储结构
3. 二叉树的顺序结构及实现
- 3.1 堆
- 3.2 堆的实现
- - 3.2.1 heap.c
  - 3.2.2 heap.c
  - 3.3.3 test.c
4. 堆排序

1. 树概念及结构

树是一种非线性的数据结构（区别于数组、链表、栈、队列等线性结构），它由 n（n≥0）个有限节点组成一个具有层次关系的集合：

像现实中的 “树”：有一个根（树根），向下分出多个分支（子树），每个分支又可以再分分支，最后是叶子；
核心特征：有且仅有一个根节点（n>0 时），除根外，每个节点有且仅有一个父节点，没有父节点的是根，没有子节点的是叶子。

如下图：

1.1 树的核心概念

如下：

根节点：树中唯一没有父节点的节点，是树的层级起点（n>0 时必存在）。
节点的度：单个节点拥有的直接子节点的个数（子节点为直接下层节点，非间接）。
树的度：树中所有节点的度数的最大值（决定树为几叉树，如度为 2 则为二叉树）。
叶子节点：度为 0的节点，也叫终端节点，无任何直接子节点，是树的层级终点。
分支节点：度≥1的节点，也叫非终端节点，包含根节点和所有有子节点的中间节点。
父 / 子节点：若节点 A 是节点 B 的直接上层节点，A 为 B 的父节点，B 为 A 的子节点；子节点有且仅有一个父节点。
兄弟节点：同一父节点的多个子节点互为兄弟节点。
节点的层次：从根节点开始计数，根为第 1 层，根的子节点为第 2 层，依次向下递增。
树的高度 / 深度：树中所有节点的最大层次数，是树的整体层级深度。
子树：树中任意一个节点及其所有后代节点构成的集合，根节点的子树为整棵树，叶子节点无子树。
森林：m≥0 棵互不相交的树的集合，将树的根节点删除，根的所有子树即构成森林。

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
孩子兄弟表示法的核心是：给每个树节点只定义两个指针：

一个指向该节点的第一个孩子（左指针）；
一个指向该节点的右兄弟（右指针）。

// 孩子兄弟表示法的节点结构体typedefstructCSNode{// 1. 节点存储的数据（如int、char等）DataType data;// 2. 左指针：指向当前节点的第一个直接子节点structCSNode*firstChild;// 3. 右指针：指向当前节点的右侧第一个兄弟节点structCSNode*rightBrother;}CSNode,*CSTree;// CSTree是指向CSNode的指针，代表树/子树

2. 二叉树

2.1 二叉树的概念

二叉树是树的特殊类型，也是实际开发中最常用的树结构，核心特征是每个节点的度≤2（即任意节点最多有两个直接子节点），且二叉树为有序树（子节点有明确的左右次序，不能随意交换）。

2.2 特殊的二叉树

2.2.1 满二叉树

定义：
所有分支节点（度 = 2）都有左、右两个孩子，且所有叶子节点都在同一层的二叉树（空二叉树也可视为特殊的满二叉树）。
核心特征：

节点数公式：高度为h的满二叉树，节点总数n=2^h−1
（比如 h=3 时，n=7；h=4 时，n=15)；
层数特征：第k层节点数 =2^k−1（每层都满，无空缺）；
叶子节点位置：全部集中在最后一层，且数量=2^h−1。

2.2.2 完全二叉树

定义：
除最后一层外，每一层的节点数都达到最大值，且最后一层的叶子节点依次靠左排列（无空缺）的二叉树。
核心特征：

满二叉树是特殊的完全二叉树（最后一层也满）；
节点数范围：高度为h的完全二叉树，2h−1≤n≤2h−1；
编号规则（根节点编号为 1，C 语言数组存储的核心）：
1.节点i的左孩子 =2i，右孩子 =2i+1；
2.节点i的父节点 =i/2（整数除法，如 i=5 的父节点是 2）；
3.若2i>n，则节点i无左孩子；若2i+1>n，则无右孩子。
叶子节点位置：仅出现在最后一层或倒数第二层，且最后一层的叶子从左到右连续。

还有斜二叉树，平衡二叉树等，这里不过多解释了

2.3 二叉树的性质

性质 1：第 k 层的最大节点数：
二叉树第 k 层（k≥1，根为第 1 层）的最大节点数为 2^k−1。例：第 1 层最多 1 个、第 2 层最多 2 个、第 3 层最多 4 个、第 5 层最多 16 个，每层节点数呈 2 倍递增。
性质 2：高度为 h 的二叉树最大总节点数：
高度为 h（h≥1）的二叉树，总节点数的最大值为 2^h−1。该值为满二叉树的节点数（每层都达到最大节点数），例：高度 3 的满二叉树，节点数 = 7；高度 4 的满二叉树，节点数 = 15。
性质 3：叶子节点与度 2 节点的核心关系（必考公式）：
任意非空二叉树中，叶子节点数（n₀）= 度为 2 的节点数（n₂）+ 1，即 n₀=n₂+1。补充：总节点数 n=n₀+n₁+n₂（n₁ 为度 1 的节点数），可联立公式互相推导。例：某二叉树有 8 个度 2 节点，则叶子节点数一定为 9；有 5 个叶子节点，则度 2 节点数一定为 4。
性质 4：空 / 单节点二叉树的特殊值：
空二叉树：高度为 0，节点数为 0；
仅根节点的二叉树：高度为 1，n₀=1、n₁=0、n₂=0（符合n₀=n₂+1）。
性质 5：高度的计算方式
有n个节点的完全二叉树，高度h=⌊log₂n⌋+1（⌊log₂n⌋ 表示对log2n向下取整）。
例：n=6时，log26≈2.58，向下取整为 2，高度 = 3；n=7时，log27≈2.8，高度 = 3；n=8时，log28=3，高度 = 4。

2.4 二叉树的存储结构

二叉树的存储结构分为顺序存储（数组）和链式存储（二叉链和三叉链）两类，核心区别在于 “是否连续存储”，适配不同的二叉树类型和操作场景。
一、顺序存储结构（基于数组）

定义
用一组连续的存储单元（数组）按层级顺序存储二叉树的节点，核心依赖 “完全二叉树的节点编号规则” 映射数组下标。
存储规则

节点按层序从 1 开始编号（根为 1），数组通常从下标 1 开始存储（下标 0 弃用，简化计算）；
编号为i的节点，存储在数组下标i的位置；
若节点不存在（非完全二叉树的空缺位置），数组对应下标留空 / 填特殊值（如 - 1）。

核心特征

优点：随机访问效率高（O (1)），无需额外存储指针，空间利用率高；
缺点：仅适合完全二叉树 / 满二叉树（非完全二叉树会出现大量空位置，浪费空间）；
关键映射关系（同完全二叉树编号规则）：
1.下标i的节点，父节点下标为⌊i/2⌋；
2.左孩子下标为2i，右孩子下标为2i+1；
3.若数组长度，则无左孩子；数组长度，则无右孩子。

适用场景

完全二叉树 / 满二叉树的存储（如堆、优先队列的底层实现）；
对访问效率要求高、节点数量固定的场景。

二、链式存储结构（最通用，分二叉链表 / 三叉链表）

二叉链表（最常用）

定义
每个节点包含 “数据域 + 两个指针域”，分别指向左孩子和右孩子，是二叉树的标准存储方式。

节点结构

数据域：存储节点的数值 / 数据；
左指针（lchild）：指向当前节点的左孩子，无左孩子则为 NULL；
右指针（rchild）：指向当前节点的右孩子，无右孩子则为 NULL。

核心特征

优点：适配所有类型二叉树（包括斜二叉树、非完全二叉树），插入 / 删除操作灵活，无空间浪费；
缺点：需额外存储指针（每个节点占 2 个指针空间），无法直接访问父节点；
空间复杂度：O(n)（n 为节点数，每个节点仅 2 个指针）。

适用场景

任意类型二叉树的存储（如二叉搜索树、平衡二叉树）；
需频繁插入 / 删除节点、节点数量动态变化的场景（如动态查找树）

3. 二叉树的顺序结构及实现

3.1 堆

堆是基于完全二叉树实现的优先队列，也是二叉树顺序存储（数组）的核心应用，本质可概括为：满足特定值规则的完全二叉树，且仅通过数组存储、仅支持堆顶的高效操作。

3.2 堆的实现

依旧分为三个部分heap.h , heap.c , test.c。

3.2.1 heap.c

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;intcapacity;}Hp;voidHeapInit(Hp*php);// 堆的销毁voidHeapDestory(Hp*php);// 堆的插入voidHeapPush(Hp*php,HPDataType x);// 堆的删除voidHeapPop(Hp*php);// 取堆顶的数据HPDataTypeHeapTop(Hp*php);// 堆的数据个数intHeapSize(Hp*php);// 堆的判空boolHeapEmpty(Hp*php);voidAdjustUp(HPDataType*a,intchild);voidAdjustDown(HPDataType*a,intn,intparent);voidSwap(HPDataType*a,HPDataType*b);voidHeapSort(int*a,intn);

3.2.2 heap.c

#define_CRT_SECURE_NO_WARNINGS#include"Heap.h"voidHeapInit(Hp*php){assert(php);php->a=NULL;php->capacity=php->size=0;}// 堆的销毁voidHeapDestory(Hp*php){assert(php);free(php->a);php->a=NULL;php->capacity=php->size=0;}voidSwap(HPDataType*a,HPDataType*b){HPDataType tmp=*a;*a=*b;*b=tmp;}voidAdjustUp(HPDataType*a,intchild){intparent=(child-1)/2;while(child>0){if(a[child]<a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}// 堆的插入voidHeapPush(Hp*php,HPDataType x){assert(php);if(php->capacity==php->size){intn=php->capacity==0?4:php->capacity*2;HPDataType*tmp=(HPDataType*)realloc(php->a,sizeof(int)*n);if(tmp==NULL){perror("realloc fail");return;}php->a=tmp;php->capacity=n;}php->a[php->size]=x;php->size++;AdjustUp(php->a,php->size-1);}voidAdjustDown(HPDataType*a,intn,intparent){intchild=parent*2+1;while(child<n){if(child+1<n&&a[child+1]<a[child]){child++;}if(a[child]<a[parent]){Swap(&a[child],&a[parent]);parent=child;child=parent*2+1;}else{break;}}}//// 堆的删除voidHeapPop(Hp*php){assert(php);assert(php->size>0);Swap(&php->a[0],&php->a[php->size-1]);php->size--;AdjustDown(php->a,php->size,0);}//// 取堆顶的数据HPDataTypeHeapTop(Hp*php){assert(php);assert(php->size>0);returnphp->a[0];}//// 堆的数据个数intHeapSize(Hp*php){assert(php);returnphp->size;}//// 堆的判空boolHeapEmpty(Hp*php){assert(php);returnphp->size==0;}

3.3.3 test.c

#define_CRT_SECURE_NO_WARNINGS#include"Heap.h"voidtestHeap1(){inta[]={4,2,8,1,5,6,9,7};for(size_ti=0;i<sizeof(a)/sizeof(a[0]);i++){AdjustUp(a,i);}intend=sizeof(a)/sizeof(a[0])-1;while(end){Swap(&a[0],&a[end]);AdjustDown(a,end,0);end--;}for(size_ti=0;i<sizeof(a)/sizeof(a[0]);i++){printf("%d ",a[i]);}}voidHeapSort(int*a,intn){for(inti=(n-2)/2;i>=0;i--){AdjustDown(a,n,i);}intend=n-1;while(end){Swap(&a[0],&a[end]);AdjustDown(a,end,0);end--;}for(inti=0;i<n;i++){printf("%d ",a[i]);}}voidtestHeap2(){inta[]={4,2,8,1,5,6,9,7};HeapSort(a,sizeof(a)/sizeof(a[0]));}intmain(){testHeap2();Hp ph;HeapInit(&ph);HeapPush(&ph,4);HeapPush(&ph,2);HeapPush(&ph,8);HeapPush(&ph,1);HeapPush(&ph,5);HeapPush(&ph,6);HeapPush(&ph,9);HeapPush(&ph,7);HeapPop(&ph);for(inti=0;i<ph.size;i++){printf("%d ",ph.a[i]);}return0;}

4. 堆排序

上面代码中有一个堆排序大家可能看不懂，这是一个比较厉害的排序，我在这分析一下
先分析向下调整：

voidAdjustDown(HPDataType*a,intn,intparent){intchild=parent*2+1;//找到子节点while(child<n){if(child+1<n&&a[child+1]<a[child])//确保不越界,找到第二层中小的那个，这也是//整个二叉树中最小的那个了{child++;}if(a[child]<a[parent]){Swap(&a[child],&a[parent]);parent=child;child=parent*2+1;}//将最小值移至第一层else{break;}}}

最坏的时间复杂的是O(logn)，即logn层。
再来分析堆排：

voidHeapSort(int*a,intn){for(inti=(n-2)/2;i>=0;i--){AdjustDown(a,n,i);}intend=n-1;while(end){Swap(&a[0],&a[end]);AdjustDown(a,end,0);end--;}for(inti=0;i<n;i++){printf("%d ",a[i]);}